dibigd::BigDigit Class Reference

Class to represent and operate on a BigDigits number. More...

Public Member Functions
	BigDigit ()
	Initialise as zero.
	BigDigit (bdigit_t x)
	Initialize with 32-bit unsigned integer.
	BigDigit (const char *str)
	Constructor for C-string literals like "0xdeadbeef".
	BigDigit (int x)
	Initialize with integer.
	BigDigit (std::string s)
	Initialise with value represented by a string, see from_str().
BigDigit	cbrt () const
	Return the integer cube root of the object's value floor(cuberoot(b))
int	cmp_ct (const BigDigit &other) const
	Compare values in constant time. More...
BigDigit	gcd (const BigDigit &other) const
	Return the greatest common divisor of this value and other.
int	getbit (size_t n) const
	Return value 1 or 0 of bit at index n. More...
bool	is_even () const
	Returns true if number is even.
bool	is_odd () const
	Returns true if number is odd.
bool	is_prime () const
	Return true if number is prime.
int	jacobi (const BigDigit &n) const
	Return the Jacobi symbol (a/n) = {-1,0,+1}. More...
BigDigit	mod_add (const BigDigit &v, const BigDigit &m) const
	Add v modulo m More...
BigDigit	mod_exp (const BigDigit &e, const BigDigit &m) const
	Compute modular exponentiation of object's value raised to power e over a modulus m. More...
BigDigit	mod_exp_ct (const BigDigit &e, const BigDigit &m) const
	Compute modular exponentiation of object's value raised to power e over a modulus m in constant time. More...
BigDigit	mod_halve (const BigDigit &p) const
	Computes u/2 (mod p) for an odd prime p. More...
BigDigit	mod_inv (const BigDigit &m) const
	Compute the inverse modulo m.
BigDigit	mod_mult (const BigDigit &y, const BigDigit &m) const
	Multiply by y modulo m.
BigDigit	mod_powerof2 (size_t L) const
	Returns a mod 2^L. More...
BigDigit	mod_sqrt (const BigDigit &p) const
	Compute a square root modulo an odd prime p. More...
BigDigit	mod_square (const BigDigit &m) const
	Square modulo m
BigDigit	mod_sub (const BigDigit &v, const BigDigit &m) const
	Subtract v modulo m. More...
BigDigit	operator& (const BigDigit &other) const
	Bitwise AND.
BigDigit	operator&= (const BigDigit &other)
	Bitwise AND Assign.
BigDigit	operator^ (const BigDigit &other) const
	Bitwise Exclusive OR (XOR)
BigDigit	operator^= (const BigDigit &other)
	Bitwise Exclusive OR Assign.
BigDigit	operator| (const BigDigit &other) const
	Bitwise OR.
BigDigit	operator|= (const BigDigit &other)
	Bitwise OR Assign.
BigDigit	operator~ () const
	Bitwise NOT. More...
BigDigit	pow (unsigned short int n) const
	Raise to the power n.
void	print () const
	Print in decimal to stdout with newline.
void	print (std::string pre) const
	Print in decimal with prefix and newline.
void	printbits () const
	Print in binary (0 and 1) with newline.
void	printbits (std::string pre) const
	Print in binary (0 and 1) with prefix and newline.
void	printhex () const
	Print in hexadecimal with newline.
void	printhex (std::string pre) const
	Print in hexadecimal with prefix and newline.
BigDigit	reverse_octets (size_t n) const
	Reverse order of octets inside BigDigit up to the n'th octet. More...
BigDigit	set_prime (size_t nbits)
	Generate a prime of exactly nbits bits using "internal" RNG. More...
BigDigit	set_prime (size_t nbits, BD_RANDFUNC UserRandFunc)
	Generate a prime of exactly nbits bits using a user-defined external RNG. More...
BigDigit	set_prime (size_t nbits, BD_RANDFUNC UserRandFunc, unsigned char *seed, size_t seedlen)
	Generate a prime of exactly nbits bits using a user-defined external RNG with a seed. More...
BigDigit	set_rand_bits (size_t nbits)
	Generate a random BIGD number of bit length at most nbits using internal RNG. More...
BigDigit	set_rand_number (const BigDigit &n)
	Generate a number at random from a uniform distribution in [0, n-1] using internal RNG. More...
BigDigit	setbit (size_t n, int value)
	Set bit at index n with value 1 or 0. More...
BigDigit	sqrt () const
	Return the integer square root of the object's value floor(sqrt(b))
BigDigit	square () const
	Compute the square. More...
std::vector< unsigned char >	to_octets () const
	Encode this BigDigit object to a byte array excluding any leading zero bytes. More...
std::vector< unsigned char >	to_octets (size_t nb) const
	Encode this BigDigit object to a byte array of exactly nb bytes. More...
bdigit_t	to_short () const
	Return the least significant digit of the object. More...
std::string	to_str () const
	Return a std::string containing the decimal representation of the BigDigit value.
std::string	to_strhex () const
	Return a std::string containing the hexadecimal representation of the BigDigit value.

Static Public Member Functions
template<typename First , typename Second >
static BigDigit	gcd (const First &first, const Second &second)
	Return GCD of a list of numbers. More...

Friends
BigDigit	from_octets (const std::vector< unsigned char > bv)
	Convert a byte array to an equivalent BigDigit. More...
BigDigit	from_str (std::string s)
	Convert the initial characters of the string s to an equivalent BigDigit. More...

Detailed Description

Class to represent and operate on a BigDigits number.

Member Function Documentation

cmp_ct()

int dibigd::BigDigit::cmp_ct

(

const BigDigit &

other

)

const

Compare values in constant time.

Returns

+1 if object's value is less than the other, 0 if equal, and -1 if greater than the other.

Remarks

Use to compare values when timing attacks are a risk.

BigDigit a = 1000;
BigDigit b = 999;
int cmp;
cmp = a.cmp_ct(b);  // +1 ==> a > b
cmp = b.cmp_ct(a);  // -1 ==> b < a
cmp = a.cmp_ct(1000); // 0 ==> a == 1000

gcd()

template<typename First , typename Second >

static BigDigit dibigd::BigDigit::gcd ( const First &  first, const Second &  second  )

inlinestatic

Return GCD of a list of numbers.

BigDigit g = BigDigit::gcd(10, 25, 30, 50);
g.print("gcd=");  // 5

getbit()

int dibigd::BigDigit::getbit

(

size_t

n

)

const

Return value 1 or 0 of bit at index n.

Remarks

bits are indexed from the right(least significant) starting at zero

jacobi()

int dibigd::BigDigit::jacobi

(

const BigDigit &

n

)

const

Return the Jacobi symbol (a/n) = {-1,0,+1}.

Remarks

If n is prime then the Jacobi symbol becomes the Legendre symbol (a/p) defined to be

• (a/p) = +1 if a is a quadratic residue modulo p
• (a/p) = -1 if a is a quadratic non-residue modulo p
• (a/p) = 0 if a is divisible by p

mod_add()

BigDigit dibigd::BigDigit::mod_add	(	const BigDigit &	v,
		const BigDigit &	m
	)		const

Add v modulo m

Parameters

v	Number to be added modulo m
m	Modulus

Returns

(u + v) mod m where u is the object's value.

Remarks

If u,v < m then this is faster than (u+v)%m.

mod_exp()

BigDigit dibigd::BigDigit::mod_exp	(	const BigDigit &	e,
		const BigDigit &	m
	)		const

Compute modular exponentiation of object's value raised to power e over a modulus m.

Not constant time. For constant time use mod_exp_ct().

Parameters

e	the exponent
m	the modulus

Returns

Value of b^e mod m

mod_exp_ct()

BigDigit dibigd::BigDigit::mod_exp_ct	(	const BigDigit &	e,
		const BigDigit &	m
	)		const

Compute modular exponentiation of object's value raised to power e over a modulus m in constant time.

Parameters

e	the exponent
m	the modulus

Returns

Value of b^e mod m

Remarks

Slower than mod_exp() but more secure where timing attacks are a risk.

mod_halve()

BigDigit dibigd::BigDigit::mod_halve

(

const BigDigit &

p

)

const

Computes u/2 (mod p) for an odd prime p.

where u is the object's value.

Remarks

Require u to be in the range [0,p-1].

mod_powerof2()

BigDigit dibigd::BigDigit::mod_powerof2

(

size_t

L

)

const

Returns a mod 2^L.

i.e. clears all bits at index greater than L.

mod_sqrt()

BigDigit dibigd::BigDigit::mod_sqrt

(

const BigDigit &

p

)

const

Compute a square root modulo an odd prime p.

Parameters

p	An odd prime.

Returns

square root modulo p or zero if error.

Remarks

Subject is expected to be a quadratic residue modulo p. The other square root is p-x. Returns 0 if root not defined.

mod_sub()

BigDigit dibigd::BigDigit::mod_sub	(	const BigDigit &	v,
		const BigDigit &	m
	)		const

Subtract v modulo m.

Parameters

v	Number to be subtracted modulo m
m	Modulus

Returns

(u - v) mod m where u is the object's value.

Remarks

This captures the case where v > u and returns u + m - v. If u,v < m then this is faster than (u-v)%m.

operator~()

BigDigit dibigd::BigDigit::operator~

(

)

const

Bitwise NOT.

Remarks

Flips all bits in every 32-bit digit up to and including the digit containing the most significant set bit. This may not be exactly what you want. Use mod_powerof2() to limit to most significant bit.

BigDigit p, q;
p = 0x5ff9;
q = ~p;
// Flips all up to next digit (32 bits)
q.printhex("NOT p="); // 0xffffa006
// Limit to stop at most significant bit
q = (~p).mod_powerof2(p.bitlen());
q.printhex("(NOT p)(mod 2^15)=");  // 0x2006

reverse_octets()

BigDigit dibigd::BigDigit::reverse_octets

(

size_t

n

)

const

Reverse order of octets inside BigDigit up to the n'th octet.

BigDigit s("0x103808afb0db2fd4abff6af4149f51b");
s.printhex("s in network order:  ");
// Set s as 128-bit little-endian number
s = s.reverse_octets(128 / 8);
s.printhex("s as 128-bit number: ");
// 0x1bf54941aff6bf4afdb20dfb8a800301

set_prime() [1/3]

BigDigit dibigd::BigDigit::set_prime

(

size_t

nbits

)

Generate a prime of exactly nbits bits using "internal" RNG.

This modifies the object.

set_prime() [2/3]

BigDigit dibigd::BigDigit::set_prime	(	size_t	nbits,
		BD_RANDFUNC	UserRandFunc
	)

Generate a prime of exactly nbits bits using a user-defined external RNG.

This modifies the object and returns the new value.

set_prime() [3/3]

BigDigit dibigd::BigDigit::set_prime	(	size_t	nbits,
		BD_RANDFUNC	UserRandFunc,
		unsigned char *	seed,
		size_t	seedlen
	)

Generate a prime of exactly nbits bits using a user-defined external RNG with a seed.

This modifies the object and returns the new value.

set_rand_bits()

BigDigit dibigd::BigDigit::set_rand_bits

(

size_t

nbits

)

Generate a random BIGD number of bit length at most nbits using internal RNG.

This modifies the object and returns the new value.

set_rand_number()

BigDigit dibigd::BigDigit::set_rand_number

(

const BigDigit &

n

)

Generate a number at random from a uniform distribution in [0, n-1] using internal RNG.

This modifies the object and returns the new value.

setbit()

BigDigit dibigd::BigDigit::setbit	(	size_t	n,
		int	value
	)

Set bit at index n with value 1 or 0.

Returns

New value.

Remarks

bits are indexed from the right (least significant) starting at zero

square()

BigDigit dibigd::BigDigit::square

(

)

const

Compute the square.

Remarks

This is the fastest way to square a number.

to_octets() [1/2]

std::vector<unsigned char> dibigd::BigDigit::to_octets

(

)

const

Encode this BigDigit object to a byte array excluding any leading zero bytes.

Remarks

The byte array is encoded in big-endian order: the first byte is the most significant.

BigDigit b(0xdeadbeef);
std::vector<unsigned char> barr = b.to_octets();
Vec::print_hex(barr); // de ad be ef

See also

from_octets

to_octets() [2/2]

std::vector<unsigned char> dibigd::BigDigit::to_octets

(

size_t

nb

)

const

Encode this BigDigit object to a byte array of exactly nb bytes.

This ensures any leading zero bytes are included.

BigDigit b(0xdeadbeef);
std::vector<unsigned char> barr = b.to_octets(6);
Vec::print_hex(barr); // 00 00 de ad be ef

Remarks

To limit to the most significant bytes, use to_octets(void)

to_short()

bdigit_t dibigd::BigDigit::to_short

(

)

const

Return the least significant digit of the object.

Remarks

Use to convert (truncate) a BigDigit object to a single digit.

Friends And Related Function Documentation

from_octets

BigDigit from_octets ( const std::vector< unsigned char >  bv )

friend

Convert a byte array to an equivalent BigDigit.

Parameters

bv	An array of bytes.

Remarks

The byte array is interpreted in big-endian order: the first byte is the most significant.

std::vector<unsigned char> bv = { 0xde, 0xad, 0xbe, 0xef };
BigDigit b = from_octets(bv);
b.printhex("b=");  // b=0xdeadbeef

See also

BigDigit::to_octets

from_str

BigDigit from_str ( std::string  s )

friend

Convert the initial characters of the string s to an equivalent BigDigit.

Parameters

s	A string of digits. A leading 0x or 0X indicates a hexadecimal (base 16) integer with valid characters [0-9a-fA-F], a leading 0b or 0B indicates a binary (base 2) integer with valid characters [01], otherwise it indicates a decimal (base 10) integer with valid characters [0-9].

Returns

A BigDigit value (zero if error).

Remarks

Leading white space characters are skipped.

BigDigit a = from_str("0xdeadbeefcafebabe");
BigDigit b = from_str("16045690984503098046");
BigDigit c = from_str("0b1101111010101101101111101110111111001010111111101011101010111110");
a.printhex("a="); b.printhex("b="); c.printhex("c=");
// a=0xdeadbeefcafebabe
// b=0xdeadbeefcafebabe
// c=0xdeadbeefcafebabe

[v1.0.1] This function is now redundant. A simple assignment is sufficient.

BigDigit a = "0xdeadbeefcafebabe";

Exceptions

std::invalid_argument

exception if an invalid character is found.