| 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 |