BigInt

BigInt is Botan’s implementation of a multiple-precision integer. Thanks to C++’s operator overloading features, using BigInt is often quite similar to using a native integer type. The number of functions related to BigInt is quite large, and not all of them are documented here. You can find the complete declarations in botan/bigint.h and botan/numthry.h.

class BigInt
BigInt(uint64_t n)

Create a BigInt with value n

BigInt(const std::string &str)

Create a BigInt from a string. By default decimal is expected. With an 0x prefix instead it is treated as hexadecimal.

BigInt(const uint8_t buf[], size_t length)

Create a BigInt from a binary array (big-endian encoding).

BigInt(RandomNumberGenerator &rng, size_t bits, bool set_high_bit = true)

Create a random BigInt of the specified size.

BigInt operator+(const BigInt &x, const BigInt &y)

Add x and y and return result.

BigInt operator+(const BigInt &x, word y)

Add x and y and return result.

BigInt operator+(word x, const BigInt &y)

Add x and y and return result.

BigInt operator-(const BigInt &x, const BigInt &y)

Subtract y from x and return result.

BigInt operator-(const BigInt &x, word y)

Subtract y from x and return result.

BigInt operator*(const BigInt &x, const BigInt &y)

Multiply x and y and return result.

BigInt operator/(const BigInt &x, const BigInt &y)

Divide x by y and return result.

BigInt operator%(const BigInt &x, const BigInt &y)

Divide x by y and return remainder.

word operator%(const BigInt &x, word y)

Divide x by y and return remainder.

word operator<<(const BigInt &x, size_t n)

Left shift x by n and return result.

word operator>>(const BigInt &x, size_t n)

Right shift x by n and return result.

BigInt &operator+=(const BigInt &y)

Add y to *this

BigInt &operator+=(word y)

Add y to *this

BigInt &operator-=(const BigInt &y)

Subtract y from *this

BigInt &operator-=(word y)

Subtract y from *this

BigInt &operator*=(const BigInt &y)

Multiply *this with y

BigInt &operator*=(word y)

Multiply *this with y

BigInt &operator/=(const BigInt &y)

Divide *this by y

BigInt &operator%=(const BigInt &y)

Divide *this by y and set *this to the remainder.

word operator%=(word y)

Divide *this by y and set *this to the remainder.

word operator<<=(size_t shift)

Left shift *this by shift bits

word operator>>=(size_t shift)

Right shift *this by shift bits

BigInt &operator++()

Increment *this by 1

BigInt &operator--()

Decrement *this by 1

BigInt operator++(int)

Postfix increment *this by 1

BigInt operator--(int)

Postfix decrement *this by 1

BigInt operator-() const

Negation operator

bool operator!() const

Return true unless *this is zero

void clear()

Set *this to zero

size_t bytes() const

Return number of bytes need to represent value of *this

size_t bits() const

Return number of bits need to represent value of *this

bool is_even() const

Return true if *this is even

bool is_odd() const

Return true if *this is odd

bool is_nonzero() const

Return true if *this is not zero

bool is_zero() const

Return true if *this is zero

void set_bit(size_t n)

Set bit n of *this

void clear_bit(size_t n)

Clear bit n of *this

bool get_bit(size_t n) const

Get bit n of *this

uint32_t to_u32bit() const

Return value of *this as a 32-bit integer, if possible. If the integer is negative or not in range, an exception is thrown.

bool is_negative() const

Return true if *this is negative

bool is_positive() const

Return true if *this is negative

BigInt abs() const

Return absolute value of *this

void binary_encode(uint8_t buf[]) const

Encode this BigInt as a big-endian integer. The sign is ignored.

void binary_decode(uint8_t buf[])

Decode this BigInt as a big-endian integer.

Number Theory

Number theoretic functions available include:

BigInt gcd(BigInt x, BigInt y)

Returns the greatest common divisor of x and y

BigInt lcm(BigInt x, BigInt y)

Returns an integer z which is the smallest integer such that z % x == 0 and z % y == 0

BigInt jacobi(BigInt a, BigInt n)

Return Jacobi symbol of (a|n).

BigInt inverse_mod(BigInt x, BigInt m)

Returns the modular inverse of x modulo m, that is, an integer y such that (x*y) % m == 1. If no such y exists, returns zero.

BigInt power_mod(BigInt b, BigInt x, BigInt m)

Returns b to the xth power modulo m. If you are doing many exponentiations with a single fixed modulus, it is faster to use a Power_Mod implementation.

BigInt ressol(BigInt x, BigInt p)

Returns the square root modulo a prime, that is, returns a number y such that (y*y) % p == x. Returns -1 if no such integer exists.

bool is_prime(BigInt n, RandomNumberGenerator &rng, size_t prob = 56, double is_random = false)

Test n for primality using a probablistic algorithm (Miller-Rabin). With this algorithm, there is some non-zero probability that true will be returned even if n is actually composite. Modifying prob allows you to decrease the chance of such a false positive, at the cost of increased runtime. Sufficient tests will be run such that the chance n is composite is no more than 1 in 2prob. Set is_random to true if (and only if) n was randomly chosen (ie, there is no danger it was chosen maliciously) as far fewer tests are needed in that case.

BigInt random_prime(RandomNumberGenerator &rng, size_t bits, BigInt coprime = 1, size_t equiv = 1, size_t equiv_mod = 2)

Return a random prime number of bits bits long that is relatively prime to coprime, and equivalent to equiv modulo equiv_mod.