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.
-
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
-
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
-
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 thanbytes()
then only the lowlen
bytes are output. Iflen
is greater thanbytes()
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
lcm
(BigInt x, BigInt y)¶ Returns an integer z which is the smallest integer such that z % x == 0 and z % y == 0
-
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 tocoprime
, and equivalent toequiv
moduloequiv_mod
.