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()

Create a BigInt with value zero

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_encode(uint8_t buf[], size_t len) const

Encode this BigInt as a big-endian integer. The sign is ignored. If len is less than bytes() then only the low len bytes are output. If len is greater than bytes() then the output is padded with leading zeros.

void binary_decode(uint8_t buf[])

Decode this BigInt as a big-endian integer.

std::string to_dec_string() const

Encode the integer as a decimal string.

std::string to_hex_string() const

Encode the integer as a hexadecimal string.

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 probabilistic 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.