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. You can find
most of them in botan/bigint.h
and botan/numthry.h
.
Note
If you can, always use expressions of the form a += b
over a =
a + b
. The difference can be very substantial, because the first
form prevents at least one needless memory allocation, and possibly
as many as three. This will be less of an issue once the library
adopts use of C++0x’s rvalue references.
Encoding Functions¶
These transform the normal representation of a BigInt
into some
other form, such as a decimal string:
-
SecureVector<byte> BigInt::encode(const BigInt &n, Encoding enc = Binary)¶
This function encodes the BigInt n into a memory vector.
Encoding
is an enum that has valuesBinary
,Octal
,Decimal
, andHexadecimal
.
-
BigInt BigInt::decode(const MemoryRegion<byte> &vec, Encoding enc)¶
Decode the integer from
vec
using the encoding specified.
These functions are static member functions, so they would be called like this:
BigInt n1 = ...; // some number
SecureVector<byte> n1_encoded = BigInt::encode(n1);
BigInt n2 = BigInt::decode(n1_encoded);
assert(n1 == n2);
There are also C++-style I/O operators defined for use with
BigInt
. The input operator understands negative numbers,
hexadecimal numbers (marked with a leading “0x”), and octal numbers
(marked with a leading ‘0’). The ‘-’ must come before the “0x” or ‘0’
marker. The output operator will never adorn the output; for example,
when printing a hexadecimal number, there will not be a leading “0x”
(though a leading ‘-’ will be printed if the number is negative). If
you want such things, you’ll have to do them yourself.
BigInt
has constructors that can create a BigInt
from an
unsigned integer or a string. You can also decode an array (a byte
pointer plus a length) into a BigInt
using a constructor.
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 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 quick_check_prime(BigInt n, RandomNumberGenerator &rng)¶
-
bool check_prime(BigInt n, RandomNumberGenerator &rng)¶
-
bool verify_prime(BigInt n, RandomNumberGenerator &rng)¶
Three variations on primality testing. All take an integer to test along with a random number generator, and return true if the integer seems like it might be prime; there is a chance that this function will return true even with a composite number. The probability decreases with the amount of work performed, so it is much less likely that
verify_prime
will return a false positive thancheck_prime
will.