BigIntegerAlgorithms.hh

   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