Commit | Line | Data |
---|---|---|
0afe80d5 MM |
1 | #ifndef BIGINTEGERALGORITHMS_H |
2 | #define BIGINTEGERALGORITHMS_H | |
3 | ||
4 | #include "BigInteger.hh" | |
5 | ||
6 | /* Some mathematical algorithms for big integers. | |
7 | * This code is new and, as such, experimental. */ | |
8 | ||
9 | // Returns the greatest common divisor of a and b. | |
10 | BigUnsigned gcd(BigUnsigned a, BigUnsigned b); | |
11 | ||
12 | /* Extended Euclidean algorithm. | |
13 | * Given m and n, finds gcd g and numbers r, s such that r*m + s*n == g. */ | |
14 | void extendedEuclidean(BigInteger m, BigInteger n, | |
15 | BigInteger &g, BigInteger &r, BigInteger &s); | |
16 | ||
17 | /* Returns the multiplicative inverse of x modulo n, or throws an exception if | |
18 | * they have a common factor. */ | |
19 | BigUnsigned modinv(const BigInteger &x, const BigUnsigned &n); | |
20 | ||
21 | // Returns (base ^ exponent) % modulus. | |
22 | BigUnsigned modexp(const BigInteger &base, const BigUnsigned &exponent, | |
23 | const BigUnsigned &modulus); | |
24 | ||
25 | #endif |