uicore::BigInt Class Reference

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)
BigInt &	operator= (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

uicore::BigInt::BigInt

(

)

Constructs a big integer (initialised to zero)

uicore::BigInt::BigInt ( uint32_t  value )

explicit

Constructs a big integer (initialised to value)

uicore::BigInt::BigInt ( int32_t  value )

explicit

Constructs a big integer (initialised to value)

uicore::BigInt::BigInt ( uint64_t  value )

explicit

Constructs a big integer (initialised to value)

uicore::BigInt::BigInt ( int64_t  value )

explicit

Constructs a big integer (initialised to value)

uicore::BigInt::BigInt

(

const BigInt &

other

)

Copy constructor.

uicore::BigInt::~BigInt

(

)

Destructor.

Member Function Documentation

void uicore::BigInt::abs

(

BigInt *

b

)

const

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

int uicore::BigInt::cmp

(

const BigInt *

b

)

const

int uicore::BigInt::cmp_d

(

uint32_t

d

)

const

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

int uicore::BigInt::cmp_z

(

)

const

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

void uicore::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 uicore::BigInt::div	(	uint32_t	d,
		BigInt *	q,
		BigInt *	r
	)		const

void uicore::BigInt::div_2

(

BigInt *

c

)

const

Compute c = a / 2, disregarding the remainder.

void uicore::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 uicore::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 uicore::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 uicore::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 uicore::BigInt::get

(

uint32_t &

d

)

Gets a value.

Throws exception if number exceeds datatype bounds

void uicore::BigInt::get

(

uint64_t &

d

)

void uicore::BigInt::get

(

int64_t &

d

)

void uicore::BigInt::get

(

int32_t &

d

)

bool uicore::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 uicore::BigInt::is_even

(

)

const

Returns a true if number is even.

bool uicore::BigInt::is_odd

(

)

const

Returns a true if number is odd.

bool uicore::BigInt::make_prime

(

unsigned int

num_bits

)

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

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

uint32_t uicore::BigInt::mod_d

(

uint32_t

d

)

const

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

void uicore::BigInt::neg

(

BigInt *

b

)

const

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

BigInt uicore::BigInt::operator%

(

const BigInt &

b

)

Compute result = this % b.

BigInt uicore::BigInt::operator%

(

uint32_t

d

)

BigInt uicore::BigInt::operator%=

(

const BigInt &

b

)

Compute this %= b.

BigInt uicore::BigInt::operator%=

(

uint32_t

d

)

BigInt uicore::BigInt::operator*

(

const BigInt &

b

)

Compute result = this * b.

BigInt uicore::BigInt::operator*

(

uint32_t

d

)

BigInt uicore::BigInt::operator*=

(

const BigInt &

b

)

Compute this *= b.

BigInt uicore::BigInt::operator*=

(

uint32_t

d

)

BigInt uicore::BigInt::operator+

(

const BigInt &

b

)

Compute result = this + b.

BigInt uicore::BigInt::operator+

(

uint32_t

d

)

BigInt uicore::BigInt::operator+=

(

const BigInt &

b

)

Compute this += b.

BigInt uicore::BigInt::operator+=

(

uint32_t

d

)

BigInt uicore::BigInt::operator-

(

const BigInt &

b

)

Compute result = this - b.

BigInt uicore::BigInt::operator-

(

uint32_t

d

)

BigInt uicore::BigInt::operator-=

(

const BigInt &

b

)

Compute this -= b.

BigInt uicore::BigInt::operator-=

(

uint32_t

d

)

BigInt uicore::BigInt::operator/

(

const BigInt &

b

)

Compute result = this / b.

BigInt uicore::BigInt::operator/

(

uint32_t

d

)

BigInt uicore::BigInt::operator/=

(

const BigInt &

b

)

Compute this /= b.

BigInt uicore::BigInt::operator/=

(

uint32_t

d

)

BigInt& uicore::BigInt::operator=

(

const BigInt &

other

)

bool uicore::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 uicore::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 uicore::BigInt::read_unsigned_octets	(	const unsigned char *	input_str,
		unsigned int	input_length
	)

void uicore::BigInt::set

(

int32_t

d

)

Sets a value.

void uicore::BigInt::set

(

uint32_t

d

)

void uicore::BigInt::set

(

uint64_t

d

)

void uicore::BigInt::set

(

int64_t

d

)

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

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

int uicore::BigInt::significant_bits

(

)

const

void uicore::BigInt::sqr

(

BigInt *

b

)

const

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

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

unsigned int uicore::BigInt::trailing_zeros

(

)

const

int uicore::BigInt::unsigned_octet_size

(

)

const

void uicore::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 uicore::BigInt::zero

(

)

---

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

• big_int.h