From 7504b3d87d6143661746d85c3c3e4052939b4e52 Mon Sep 17 00:00:00 2001 From: Bo Xu Date: Tue, 2 Dec 2014 13:06:22 -0800 Subject: Initial check in of big integer library, v2010.04.30 R=tsepez@chromium.org Review URL: https://codereview.chromium.org/773443004 --- third_party/bigint/BigIntegerAlgorithms.hh | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) create mode 100644 third_party/bigint/BigIntegerAlgorithms.hh (limited to 'third_party/bigint/BigIntegerAlgorithms.hh') diff --git a/third_party/bigint/BigIntegerAlgorithms.hh b/third_party/bigint/BigIntegerAlgorithms.hh new file mode 100644 index 0000000000..b1dd943227 --- /dev/null +++ b/third_party/bigint/BigIntegerAlgorithms.hh @@ -0,0 +1,25 @@ +#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 -- cgit v1.2.3