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 values Binary, Octal, Decimal, and Hexadecimal.
- 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 than check_prime will.