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)
 
BigIntoperator= (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 ()
 

Detailed Description

Big Integer class.

Constructor & Destructor Documentation

◆ BigInt() [1/6]

◆ BigInt() [2/6]

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

Constructs a big integer (initialised to value)

◆ BigInt() [3/6]

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

Constructs a big integer (initialised to value)

◆ BigInt() [4/6]

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

Constructs a big integer (initialised to value)

◆ BigInt() [5/6]

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

Constructs a big integer (initialised to value)

◆ BigInt() [6/6]

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

Copy constructor.

References BigInt().

◆ ~BigInt()

clan::BigInt::~BigInt ( )

Destructor.

Member Function Documentation

◆ abs()

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

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

References BigInt(), and clan::b.

◆ cmp()

int clan::BigInt::cmp ( const BigInt * b) const

References BigInt(), and clan::b.

◆ cmp_d()

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.

◆ cmp_z()

int clan::BigInt::cmp_z ( ) const

Compare a <=> 0. Returns <0 if a<0, 0 if a=0, >0 if a>0.

◆ div() [1/2]

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)

References BigInt(), clan::b, clan::q, and clan::r.

◆ div() [2/2]

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

References BigInt(), clan::d, clan::q, and clan::r.

◆ div_2()

void clan::BigInt::div_2 ( BigInt * c) const

Compute c = a / 2, disregarding the remainder.

References BigInt(), and clan::c.

◆ div_d()

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).

References BigInt(), clan::d, clan::q, and clan::r.

◆ exch()

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().

◆ exptmod()

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)

References BigInt(), clan::b, clan::c, and clan::m.

◆ fermat()

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.

◆ get() [1/4]

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

References clan::d.

◆ get() [2/4]

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

References clan::d.

◆ get() [3/4]

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

Gets a value.

Throws exception if number exceeds datatype bounds

References clan::d.

◆ get() [4/4]

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

References clan::d.

◆ invmod()

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.

References BigInt(), clan::c, and clan::m.

◆ is_even()

bool clan::BigInt::is_even ( ) const

Returns a true if number is even.

◆ is_odd()

bool clan::BigInt::is_odd ( ) const

Returns a true if number is odd.

◆ make_prime()

bool clan::BigInt::make_prime ( unsigned int num_bits)

◆ mod()

void clan::BigInt::mod ( const BigInt * m,
BigInt * c ) const

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

References BigInt(), clan::c, and clan::m.

◆ mod_d()

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.

◆ neg()

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

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

References BigInt(), and clan::b.

◆ operator%() [1/2]

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

Compute result = this % b.

References BigInt(), and clan::b.

◆ operator%() [2/2]

BigInt clan::BigInt::operator% ( uint32_t d)

References BigInt(), and clan::d.

◆ operator%=() [1/2]

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

Compute this %= b.

References BigInt(), and clan::b.

◆ operator%=() [2/2]

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

References BigInt(), and clan::d.

◆ operator*() [1/2]

BigInt clan::BigInt::operator* ( const BigInt & b)

Compute result = this * b.

References BigInt(), and clan::b.

◆ operator*() [2/2]

BigInt clan::BigInt::operator* ( uint32_t d)

References BigInt(), and clan::d.

◆ operator*=() [1/2]

BigInt clan::BigInt::operator*= ( const BigInt & b)

Compute this *= b.

References BigInt(), and clan::b.

◆ operator*=() [2/2]

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

References BigInt(), and clan::d.

◆ operator+() [1/2]

BigInt clan::BigInt::operator+ ( const BigInt & b)

Compute result = this + b.

References BigInt(), and clan::b.

◆ operator+() [2/2]

BigInt clan::BigInt::operator+ ( uint32_t d)

References BigInt(), and clan::d.

◆ operator+=() [1/2]

BigInt clan::BigInt::operator+= ( const BigInt & b)

Compute this += b.

References BigInt(), and clan::b.

◆ operator+=() [2/2]

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

References BigInt(), and clan::d.

◆ operator-() [1/2]

BigInt clan::BigInt::operator- ( const BigInt & b)

Compute result = this - b.

References BigInt(), and clan::b.

◆ operator-() [2/2]

BigInt clan::BigInt::operator- ( uint32_t d)

References BigInt(), and clan::d.

◆ operator-=() [1/2]

BigInt clan::BigInt::operator-= ( const BigInt & b)

Compute this -= b.

References BigInt(), and clan::b.

◆ operator-=() [2/2]

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

References BigInt(), and clan::d.

◆ operator/() [1/2]

BigInt clan::BigInt::operator/ ( const BigInt & b)

Compute result = this / b.

References BigInt(), and clan::b.

◆ operator/() [2/2]

BigInt clan::BigInt::operator/ ( uint32_t d)

References BigInt(), and clan::d.

◆ operator/=() [1/2]

BigInt clan::BigInt::operator/= ( const BigInt & b)

Compute this /= b.

References BigInt(), and clan::b.

◆ operator/=() [2/2]

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

References BigInt(), and clan::d.

◆ operator=()

BigInt & clan::BigInt::operator= ( const BigInt & other)

References BigInt().

◆ pprime()

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

◆ random()

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.

◆ read_unsigned_octets()

void clan::BigInt::read_unsigned_octets ( const unsigned char * input_str,
unsigned int input_length )

◆ set() [1/4]

void clan::BigInt::set ( int32_t d)

Sets a value.

References clan::d.

◆ set() [2/4]

void clan::BigInt::set ( int64_t d)

References clan::d.

◆ set() [3/4]

void clan::BigInt::set ( uint32_t d)

References clan::d.

◆ set() [4/4]

void clan::BigInt::set ( uint64_t d)

References clan::d.

◆ set_bit()

void clan::BigInt::set_bit ( unsigned int bit_number,
unsigned int value )

◆ sieve()

void clan::BigInt::sieve ( const uint32_t * primes,
unsigned int num_primes,
std::vector< unsigned char > & sieve )

References sieve().

Referenced by sieve().

◆ significant_bits()

int clan::BigInt::significant_bits ( ) const

◆ sqr()

void clan::BigInt::sqr ( BigInt * b) const

References BigInt(), and clan::b.

◆ sqrmod()

void clan::BigInt::sqrmod ( const BigInt * m,
BigInt * c ) const

References BigInt(), clan::c, and clan::m.

◆ to_unsigned_octets()

void clan::BigInt::to_unsigned_octets ( unsigned char * output_str,
unsigned int output_length ) const

◆ trailing_zeros()

unsigned int clan::BigInt::trailing_zeros ( ) const

◆ unsigned_octet_size()

int clan::BigInt::unsigned_octet_size ( ) const

◆ xgcd()

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()

References BigInt(), clan::b, clan::g, clan::x, and clan::y.

◆ zero()

void clan::BigInt::zero ( )

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