Initial check in of big integer library, v2010.04.30

R=tsepez@chromium.org

Review URL: https://codereview.chromium.org/773443004

1 files changed, 25 insertions, 0 deletions

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