| #ifndef BIGINTEGERALGORITHMS_H |
| #define BIGINTEGERALGORITHMS_H |
| |
| #include "BigInteger.hh" |
| |
| /* Some mathematical algorithms for big integers. |
| * This code is new and, as such, experimental. */ |
| |
| // Returns the greatest common divisor of a and b. |
| BigUnsigned gcd(BigUnsigned a, BigUnsigned b); |
| |
| /* Extended Euclidean algorithm. |
| * Given m and n, finds gcd g and numbers r, s such that r*m + s*n == g. */ |
| void extendedEuclidean(BigInteger m, BigInteger n, |
| BigInteger &g, BigInteger &r, BigInteger &s); |
| |
| /* Returns the multiplicative inverse of x modulo n, or throws an exception if |
| * they have a common factor. */ |
| BigUnsigned modinv(const BigInteger &x, const BigUnsigned &n); |
| |
| // Returns (base ^ exponent) % modulus. |
| BigUnsigned modexp(const BigInteger &base, const BigUnsigned &exponent, |
| const BigUnsigned &modulus); |
| |
| #endif |
