yosys/libs/bigint/BigIntegerAlgorithms.hh

26 lines
826 B
C++
Raw Permalink Normal View History

2013-01-05 04:13:26 -06:00
#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