Initial check in of big integer library

third_party/bigint/BigIntegerAlgorithms.hh

Index: third_party/bigint/BigIntegerAlgorithms.hh
diff --git a/third_party/bigint/BigIntegerAlgorithms.hh b/third_party/bigint/BigIntegerAlgorithms.hh
new file mode 100644
index 0000000000000000000000000000000000000000..b1dd9432274b77856efaf35706f39dced49f3663
--- /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