Initial check in of big integer library, v2010.04.30
[pdfium.git] / third_party / bigint / 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