[bigint/bigint.git] / BigIntegerAlgorithms.hh

#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
Commit	Line	Data
0afe80d5 MM	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 rm + sn == 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