Big Integer class. More...
#include <big_int.h>
Public Member Functions | |
BigInt () | |
Constructs a big integer (initialised to zero) | |
BigInt (const BigInt &other) | |
Copy constructor. | |
BigInt (int32_t value) | |
Constructs a big integer (initialised to value) | |
BigInt (int64_t value) | |
Constructs a big integer (initialised to value) | |
BigInt (uint32_t value) | |
Constructs a big integer (initialised to value) | |
BigInt (uint64_t value) | |
Constructs a big integer (initialised to value) | |
~BigInt () | |
Destructor. | |
void | abs (BigInt *b) const |
Compute b = |a|. 'a' and 'b' may be identical. | |
int | cmp (const BigInt *b) const |
int | cmp_d (uint32_t d) const |
Compare a <=> d. Returns <0 if a<d, 0 if a=d, >0 if a>d. | |
int | cmp_z () const |
Compare a <=> 0. Returns <0 if a<0, 0 if a=0, >0 if a>0. | |
void | div (const BigInt &b, BigInt *q, BigInt *r) const |
Compute q = a / b and r = a mod b. | |
void | div (uint32_t d, BigInt *q, BigInt *r) const |
void | div_2 (BigInt *c) const |
Compute c = a / 2, disregarding the remainder. | |
void | div_d (uint32_t d, BigInt *q, uint32_t *r) const |
Compute the quotient q = a / d and remainder r = a mod d, for a single digit d. Respects the sign of its divisor (single digits are unsigned anyway). | |
void | exch (BigInt *mp2) |
Exchange mp1 and mp2 without allocating any intermediate memory. | |
void | exptmod (const BigInt *b, const BigInt *m, BigInt *c) const |
Compute c = (a ** b) mod m. | |
bool | fermat (uint32_t w) const |
Using w as a witness, try pseudo-primality testing based on Fermat's little theorem. | |
void | get (int32_t &d) |
void | get (int64_t &d) |
void | get (uint32_t &d) |
Gets a value. | |
void | get (uint64_t &d) |
bool | invmod (const BigInt *m, BigInt *c) const |
Compute c = a^-1 (mod m), if there is an inverse for a (mod m). | |
bool | is_even () const |
Returns a true if number is even. | |
bool | is_odd () const |
Returns a true if number is odd. | |
bool | make_prime (unsigned int num_bits) |
void | mod (const BigInt *m, BigInt *c) const |
Compute c = a (mod m). Result will always be 0 <= c < m. | |
uint32_t | mod_d (uint32_t d) const |
Compute c = a (mod d). Result will always be 0 <= c < d. | |
void | neg (BigInt *b) const |
Compute b = -a. 'a' and 'b' may be identical. | |
BigInt | operator% (const BigInt &b) |
Compute result = this % b. | |
BigInt | operator% (uint32_t d) |
BigInt | operator%= (const BigInt &b) |
Compute this %= b. | |
BigInt | operator%= (uint32_t d) |
BigInt | operator* (const BigInt &b) |
Compute result = this * b. | |
BigInt | operator* (uint32_t d) |
BigInt | operator*= (const BigInt &b) |
Compute this *= b. | |
BigInt | operator*= (uint32_t d) |
BigInt | operator+ (const BigInt &b) |
Compute result = this + b. | |
BigInt | operator+ (uint32_t d) |
BigInt | operator+= (const BigInt &b) |
Compute this += b. | |
BigInt | operator+= (uint32_t d) |
BigInt | operator- (const BigInt &b) |
Compute result = this - b. | |
BigInt | operator- (uint32_t d) |
BigInt | operator-= (const BigInt &b) |
Compute this -= b. | |
BigInt | operator-= (uint32_t d) |
BigInt | operator/ (const BigInt &b) |
Compute result = this / b. | |
BigInt | operator/ (uint32_t d) |
BigInt | operator/= (const BigInt &b) |
Compute this /= b. | |
BigInt | operator/= (uint32_t d) |
BigInt & | operator= (const BigInt &other) |
bool | pprime (int nt) const |
Performs nt iteration of the Miller-Rabin probabilistic primality test on a. | |
void | random () |
Assigns a random value to a. | |
void | read_unsigned_octets (const unsigned char *input_str, unsigned int input_length) |
void | set (int32_t d) |
Sets a value. | |
void | set (int64_t d) |
void | set (uint32_t d) |
void | set (uint64_t d) |
void | set_bit (unsigned int bit_number, unsigned int value) |
void | sieve (const uint32_t *primes, unsigned int num_primes, std::vector< unsigned char > &sieve) |
int | significant_bits () const |
void | sqr (BigInt *b) const |
void | sqrmod (const BigInt *m, BigInt *c) const |
void | to_unsigned_octets (unsigned char *output_str, unsigned int output_length) const |
unsigned int | trailing_zeros () const |
int | unsigned_octet_size () const |
void | xgcd (const BigInt *b, BigInt *g, BigInt *x, BigInt *y) const |
Compute g = (a, b) and values x and y satisfying Bezout's identity. | |
void | zero () |
Big Integer class.
clan::BigInt::BigInt | ( | ) |
Constructs a big integer (initialised to zero)
Referenced by BigInt(), abs(), cmp(), div(), div(), div_2(), div_d(), exch(), exptmod(), invmod(), mod(), neg(), operator%(), operator%(), operator%=(), operator%=(), operator*(), operator*(), operator*=(), operator*=(), operator+(), operator+(), operator+=(), operator+=(), operator-(), operator-(), operator-=(), operator-=(), operator/(), operator/(), operator/=(), operator/=(), operator=(), sqr(), sqrmod(), and xgcd().
|
explicit |
Constructs a big integer (initialised to value)
|
explicit |
Constructs a big integer (initialised to value)
|
explicit |
Constructs a big integer (initialised to value)
|
explicit |
Constructs a big integer (initialised to value)
clan::BigInt::~BigInt | ( | ) |
Destructor.
void clan::BigInt::abs | ( | BigInt * | b | ) | const |
int clan::BigInt::cmp_d | ( | uint32_t | d | ) | const |
Compare a <=> d. Returns <0 if a<d, 0 if a=d, >0 if a>d.
References clan::d.
int clan::BigInt::cmp_z | ( | ) | const |
Compare a <=> 0. Returns <0 if a<0, 0 if a=0, >0 if a>0.
void clan::BigInt::div_2 | ( | BigInt * | c | ) | const |
void clan::BigInt::div_d | ( | uint32_t | d, |
BigInt * | q, | ||
uint32_t * | r ) const |
void clan::BigInt::exch | ( | BigInt * | mp2 | ) |
Exchange mp1 and mp2 without allocating any intermediate memory.
(well, unless you count the stack space needed for this call and the locals it creates...). This cannot fail.
References BigInt().
Compute c = (a ** b) mod m.
Uses a standard square-and-multiply method with modular reductions at each step. (This is basically the same code as expt(), except for the addition of the reductions)
The modular reductions are done using Barrett's algorithm (see reduce() for details)
bool clan::BigInt::fermat | ( | uint32_t | w | ) | const |
Using w as a witness, try pseudo-primality testing based on Fermat's little theorem.
If a is prime, and (w, a) = 1, then w^a == w (mod a). So, we compute z = w^a (mod a) and compare z to w; if they are equal, the test passes and we return true. Otherwise, we return false.
References clan::w.
void clan::BigInt::get | ( | int32_t & | d | ) |
References clan::d.
void clan::BigInt::get | ( | int64_t & | d | ) |
References clan::d.
void clan::BigInt::get | ( | uint32_t & | d | ) |
void clan::BigInt::get | ( | uint64_t & | d | ) |
References clan::d.
bool clan::BigInt::is_even | ( | ) | const |
Returns a true if number is even.
bool clan::BigInt::is_odd | ( | ) | const |
Returns a true if number is odd.
bool clan::BigInt::make_prime | ( | unsigned int | num_bits | ) |
uint32_t clan::BigInt::mod_d | ( | uint32_t | d | ) | const |
Compute c = a (mod d). Result will always be 0 <= c < d.
References clan::d.
void clan::BigInt::neg | ( | BigInt * | b | ) | const |
bool clan::BigInt::pprime | ( | int | nt | ) | const |
Performs nt iteration of the Miller-Rabin probabilistic primality test on a.
Returns true if the tests pass, false if one fails. If false is returned, the number is definitely composite. If true
void clan::BigInt::random | ( | ) |
Assigns a random value to a.
This value is generated using the standard C library's rand() function, so it should not be used for cryptographic purposes, but it should be fine for primality testing, since all we really care about there is reasonable statistical properties. As many digits as a currently has are filled with random digits.
void clan::BigInt::read_unsigned_octets | ( | const unsigned char * | input_str, |
unsigned int | input_length ) |
void clan::BigInt::set | ( | int32_t | d | ) |
Sets a value.
References clan::d.
void clan::BigInt::set | ( | int64_t | d | ) |
References clan::d.
void clan::BigInt::set | ( | uint32_t | d | ) |
References clan::d.
void clan::BigInt::set | ( | uint64_t | d | ) |
References clan::d.
void clan::BigInt::set_bit | ( | unsigned int | bit_number, |
unsigned int | value ) |
void clan::BigInt::sieve | ( | const uint32_t * | primes, |
unsigned int | num_primes, | ||
std::vector< unsigned char > & | sieve ) |
int clan::BigInt::significant_bits | ( | ) | const |
void clan::BigInt::to_unsigned_octets | ( | unsigned char * | output_str, |
unsigned int | output_length ) const |
unsigned int clan::BigInt::trailing_zeros | ( | ) | const |
int clan::BigInt::unsigned_octet_size | ( | ) | const |
void clan::BigInt::zero | ( | ) |