X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/blobdiff_plain/3e1327901d299a537a8d932c49dd330f87ac3bda..0afe80d551aa9b66b574b956cf681692399fc728:/BigIntegerAlgorithms.hh

diff --git a/BigIntegerAlgorithms.hh b/BigIntegerAlgorithms.hh
new file mode 100644
index 0000000..b1dd943
--- /dev/null
+++ b/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