Big Integer class. More...

#include <big_int.h>

Public Member Functions

 BigInt ()
 Constructs a big integer (initialised to zero) More...
 
 BigInt (uint32_t value)
 Constructs a big integer (initialised to value) More...
 
 BigInt (int32_t value)
 Constructs a big integer (initialised to value) More...
 
 BigInt (uint64_t value)
 Constructs a big integer (initialised to value) More...
 
 BigInt (int64_t value)
 Constructs a big integer (initialised to value) More...
 
 BigInt (const BigInt &other)
 Copy constructor. More...
 
 ~BigInt ()
 Destructor. More...
 
void abs (BigInt *b) const
 Compute b = |a|. 'a' and 'b' may be identical. More...
 
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. More...
 
int cmp_z () const
 Compare a <=> 0. Returns <0 if a<0, 0 if a=0, >0 if a>0. More...
 
void div (const BigInt &b, BigInt *q, BigInt *r) const
 Compute q = a / b and r = a mod b. More...
 
void div (uint32_t d, BigInt *q, BigInt *r) const
 
void div_2 (BigInt *c) const
 Compute c = a / 2, disregarding the remainder. More...
 
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). More...
 
void exch (BigInt *mp2)
 Exchange mp1 and mp2 without allocating any intermediate memory. More...
 
void exptmod (const BigInt *b, const BigInt *m, BigInt *c) const
 Compute c = (a ** b) mod m. More...
 
bool fermat (uint32_t w) const
 Using w as a witness, try pseudo-primality testing based on Fermat's little theorem. More...
 
void get (uint32_t &d)
 Gets a value. More...
 
void get (uint64_t &d)
 
void get (int64_t &d)
 
void get (int32_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). More...
 
bool is_even () const
 Returns a true if number is even. More...
 
bool is_odd () const
 Returns a true if number is odd. More...
 
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. More...
 
uint32_t mod_d (uint32_t d) const
 Compute c = a (mod d). Result will always be 0 <= c < d. More...
 
void neg (BigInt *b) const
 Compute b = -a. 'a' and 'b' may be identical. More...
 
BigInt operator% (const BigInt &b)
 Compute result = this % b. More...
 
BigInt operator% (uint32_t d)
 
BigInt operator%= (const BigInt &b)
 Compute this %= b. More...
 
BigInt operator%= (uint32_t d)
 
BigInt operator* (const BigInt &b)
 Compute result = this * b. More...
 
BigInt operator* (uint32_t d)
 
BigInt operator*= (const BigInt &b)
 Compute this *= b. More...
 
BigInt operator*= (uint32_t d)
 
BigInt operator+ (const BigInt &b)
 Compute result = this + b. More...
 
BigInt operator+ (uint32_t d)
 
BigInt operator+= (const BigInt &b)
 Compute this += b. More...
 
BigInt operator+= (uint32_t d)
 
BigInt operator- (const BigInt &b)
 Compute result = this - b. More...
 
BigInt operator- (uint32_t d)
 
BigInt operator-= (const BigInt &b)
 Compute this -= b. More...
 
BigInt operator-= (uint32_t d)
 
BigInt operator/ (const BigInt &b)
 Compute result = this / b. More...
 
BigInt operator/ (uint32_t d)
 
BigInt operator/= (const BigInt &b)
 Compute this /= b. More...
 
BigInt operator/= (uint32_t d)
 
BigIntoperator= (const BigInt &other)
 
bool pprime (int nt) const
 Performs nt iteration of the Miller-Rabin probabilistic primality test on a. More...
 
void random ()
 Assigns a random value to a. More...
 
void read_unsigned_octets (const unsigned char *input_str, unsigned int input_length)
 
void set (int32_t d)
 Sets a value. More...
 
void set (uint32_t d)
 
void set (uint64_t d)
 
void set (int64_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. More...
 
void zero ()
 

Detailed Description

Big Integer class.

Constructor & Destructor Documentation

clan::BigInt::BigInt ( )

Constructs a big integer (initialised to zero)

clan::BigInt::BigInt ( uint32_t  value)
explicit

Constructs a big integer (initialised to value)

clan::BigInt::BigInt ( int32_t  value)
explicit

Constructs a big integer (initialised to value)

clan::BigInt::BigInt ( uint64_t  value)
explicit

Constructs a big integer (initialised to value)

clan::BigInt::BigInt ( int64_t  value)
explicit

Constructs a big integer (initialised to value)

clan::BigInt::BigInt ( const BigInt other)

Copy constructor.

clan::BigInt::~BigInt ( )

Destructor.

Member Function Documentation

void clan::BigInt::abs ( BigInt b) const

Compute b = |a|. 'a' and 'b' may be identical.

int clan::BigInt::cmp ( const 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.

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 ( const BigInt b,
BigInt q,
BigInt r 
) const

Compute q = a / b and r = a mod b.

Input parameters may be re-used as output parameters. If q or r is NULL, that portion of the computation will be discarded (although it will still be computed)

void clan::BigInt::div ( uint32_t  d,
BigInt q,
BigInt r 
) const
void clan::BigInt::div_2 ( BigInt c) const

Compute c = a / 2, disregarding the remainder.

void clan::BigInt::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 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.

void clan::BigInt::exptmod ( const BigInt b,
const BigInt m,
BigInt c 
) const

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.

void clan::BigInt::get ( uint32_t &  d)

Gets a value.

Throws exception if number exceeds datatype bounds

void clan::BigInt::get ( uint64_t &  d)
void clan::BigInt::get ( int64_t &  d)
void clan::BigInt::get ( int32_t &  d)
bool clan::BigInt::invmod ( const BigInt m,
BigInt c 
) const

Compute c = a^-1 (mod m), if there is an inverse for a (mod m).

This is equivalent to the question of whether (a, m) = 1. If not, false is returned, and there is no inverse.

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)
void clan::BigInt::mod ( const BigInt m,
BigInt c 
) const

Compute c = a (mod m). Result will always be 0 <= c < m.

uint32_t clan::BigInt::mod_d ( uint32_t  d) const

Compute c = a (mod d). Result will always be 0 <= c < d.

void clan::BigInt::neg ( BigInt b) const

Compute b = -a. 'a' and 'b' may be identical.

BigInt clan::BigInt::operator% ( const BigInt b)

Compute result = this % b.

BigInt clan::BigInt::operator% ( uint32_t  d)
BigInt clan::BigInt::operator%= ( const BigInt b)

Compute this %= b.

BigInt clan::BigInt::operator%= ( uint32_t  d)
BigInt clan::BigInt::operator* ( const BigInt b)

Compute result = this * b.

BigInt clan::BigInt::operator* ( uint32_t  d)
BigInt clan::BigInt::operator*= ( const BigInt b)

Compute this *= b.

BigInt clan::BigInt::operator*= ( uint32_t  d)
BigInt clan::BigInt::operator+ ( const BigInt b)

Compute result = this + b.

BigInt clan::BigInt::operator+ ( uint32_t  d)
BigInt clan::BigInt::operator+= ( const BigInt b)

Compute this += b.

BigInt clan::BigInt::operator+= ( uint32_t  d)
BigInt clan::BigInt::operator- ( const BigInt b)

Compute result = this - b.

BigInt clan::BigInt::operator- ( uint32_t  d)
BigInt clan::BigInt::operator-= ( const BigInt b)

Compute this -= b.

BigInt clan::BigInt::operator-= ( uint32_t  d)
BigInt clan::BigInt::operator/ ( const BigInt b)

Compute result = this / b.

BigInt clan::BigInt::operator/ ( uint32_t  d)
BigInt clan::BigInt::operator/= ( const BigInt b)

Compute this /= b.

BigInt clan::BigInt::operator/= ( uint32_t  d)
BigInt& clan::BigInt::operator= ( const BigInt other)
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.

void clan::BigInt::set ( uint32_t  d)
void clan::BigInt::set ( uint64_t  d)
void clan::BigInt::set ( int64_t  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::sqr ( BigInt b) const
void clan::BigInt::sqrmod ( const BigInt m,
BigInt c 
) 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::xgcd ( const BigInt b,
BigInt g,
BigInt x,
BigInt y 
) const

Compute g = (a, b) and values x and y satisfying Bezout's identity.

(that is, ax + by = g). This uses the extended binary GCD algorithm based on the Stein algorithm used for mp_gcd()

void clan::BigInt::zero ( )

The documentation for this class was generated from the following file: