Overview

Interface to core BigDigits "mp" functions using fixed-length arrays.

Typedefs
typedef uint32_t	DIGIT_T
	The basic BigDigit element, an unsigned 32-bit integer. More...

Functions
u32	mpAdd (u32 w[], const u32 u[], const u32 v[], size_t ndigits)
	Computes w = u + v, returns carry. More...

u32	mpSubtract (u32 w[], const u32 u[], const u32 v[], size_t ndigits)
	Computes w = u - v, returns borrow. More...

int	mpMultiply (u32 w[], const u32 u[], const u32 v[], size_t ndigits)
	Computes product w = u * v. More...

int	mpDivide (u32 q[], u32 r[], const u32 u[], size_t udigits, u32 v[], size_t vdigits)
	Computes integer division of u by v such that u=qv+r. More...

int	mpModulo (u32 r[], const u32 u[], size_t udigits, u32 v[], size_t vdigits)
	Computes remainder r = u mod v. More...

int	mpSquare (u32 w[], const u32 x[], size_t ndigits)
	Computes square w = x^2. More...

int	mpSqrt (u32 s[], const u32 x[], size_t ndigits)
	Computes integer square root s = floor(sqrt(x)) More...

int	mpCubeRoot (u32 s[], const u32 x[], size_t ndigits)
	Computes integer cube root s = floor(cuberoot(x)) More...

int	mpEqual (const u32 a[], const u32 b[], size_t ndigits)
	Returns true if a == b, else false, using constant-time algorithm. More...

int	mpCompare (const u32 a[], const u32 b[], size_t ndigits)
	Returns sign of `(a-b)` as `{-1,0,+1}` using constant-time algorithm. More...

int	mpIsZero (const u32 a[], size_t ndigits)
	Returns true if a is zero, else false, using constant-time algorithm. More...

int	mpEqual_q (const u32 a[], const u32 b[], size_t ndigits)
	Returns true if a == b, else false (quick) More...

int	mpCompare_q (const u32 a[], const u32 b[], size_t ndigits)
	Returns sign of `(a-b)` as `{-1,0,+1}` (quick) More...

int	mpIsZero_q (const u32 a[], size_t ndigits)
	Returns true if a is zero, else false (quick) More...

int	mpModExp (u32 y[], const u32 x[], const u32 e[], u32 m[], size_t ndigits)
	Computes y = x^e mod m. More...

int	mpModExp_ct (u32 yout[], const u32 x[], const u32 e[], u32 m[], size_t ndigits)
	Computes y = x^e mod m in constant time. More...

int	mpModMult (u32 a[], const u32 x[], const u32 y[], u32 m[], size_t ndigits)
	Computes a = (x * y) mod m. More...

int	mpModInv (u32 inv[], const u32 u[], const u32 m[], size_t ndigits)
	Computes the inverse of `u` modulo `m`, inv = u^{-1} mod m. More...

int	mpGcd (u32 g[], const u32 x[], const u32 y[], size_t ndigits)
	Computes g = gcd(x, y), the greatest common divisor of x and y. More...

int	mpJacobi (const u32 a[], const u32 n[], size_t ndigits)
	Returns the Jacobi symbol (a/n) in {-1, 0, +1}. More...

size_t	mpBitLength (const u32 a[], size_t ndigits)
	Returns number of significant bits in a. More...

u32	mpShiftLeft (u32 a[], const u32 b[], size_t x, size_t ndigits)
	Computes a = b << x. More...

u32	mpShiftRight (u32 a[], const u32 b[], size_t x, size_t ndigits)
	Computes a = b >> x. More...

void	mpXorBits (u32 a[], const u32 b[], const u32 c[], size_t ndigits)
	Computes bitwise a = b XOR c. More...

void	mpOrBits (u32 a[], const u32 b[], const u32 c[], size_t ndigits)
	Computes bitwise a = b OR c. More...

void	mpAndBits (u32 a[], const u32 b[], const u32 c[], size_t ndigits)
	Computes bitwise a = b AND c. More...

void	mpNotBits (u32 a[], const u32 b[], size_t ndigits)
	Computes bitwise a = NOT b. More...

void	mpModPowerOf2 (u32 a[], size_t ndigits, size_t L)
	Computes a = a mod 2^L, ie clears all bits greater than L. More...

int	mpSetBit (u32 a[], size_t ndigits, size_t n, int value)
	Sets bit n of a (0..nbits-1) with value 1 or 0. More...

int	mpGetBit (u32 a[], size_t ndigits, size_t n)
	Returns value 1 or 0 of bit n (0..nbits-1) More...

u32	mpSetZero (u32 a[], size_t ndigits)
	Sets a = 0. More...

void	mpSetDigit (u32 a[], u32 d, size_t ndigits)
	Sets a = d where d is a single digit. More...

void	mpSetEqual (u32 a[], const u32 b[], size_t ndigits)
	Sets a = b. More...

size_t	mpSizeof (const u32 a[], size_t ndigits)
	Returns number of significant non-zero digits in a. More...

int	mpIsPrime (u32 w[], size_t ndigits, size_t t)
	Returns true (1) if `w` is probably prime. More...

int	mpRabinMiller (u32 w[], size_t ndigits, size_t t)
	Returns true (1) if `w` is probably prime using just the Rabin-Miller test. More...

u32	mpShortAdd (u32 w[], const u32 u[], u32 d, size_t ndigits)
	Computes w = u + d, returns carry. More...

u32	mpShortSub (u32 w[], const u32 u[], u32 d, size_t ndigits)
	Computes w = u - d, returns borrow. More...

u32	mpShortMult (u32 p[], const u32 x[], u32 d, size_t ndigits)
	Computes product p = x * d. More...

u32	mpShortDiv (u32 q[], const u32 u[], u32 d, size_t ndigits)
	Computes quotient q = u div d, returns remainder. More...

u32	mpShortMod (const u32 a[], u32 d, size_t ndigits)
	Computes remainder r = a mod d. More...

int	mpShortCmp (const u32 a[], u32 d, size_t ndigits)
	Returns sign of (a - d) where d is a single digit. More...

int	spMultiply (u32 p[2], u32 x, u32 y)
	Computes p = x * y, where x and y are single digits. More...

u32	spDivide (u32 q, u32 r, const u32 u[2], u32 v)
	Computes quotient q = u div v, remainder r = u mod v, where q, r and v are single digits. More...

u32	spSimpleRand (u32 lower, u32 upper)
	Returns a simple pseudo-random digit between lower and upper. More...

size_t	mpQuickRandBits (u32 a[], size_t ndigits, size_t nbits)
	Generate a quick-and-dirty random mp number a of bit length at most `nbits` using plain-old-rand. More...

void	mpPrintHex (const char prefix, const u32 p, size_t ndigits, const char *suffix)
	Print in hex format with optional prefix and suffix strings. More...

void	mpPrint (const u32 *p, size_t ndigits)
	Print in decimal format with optional prefix and suffix strings. More...

void	mpPrintNL (const u32 *p, size_t ndigits)
	Print all digits in hex with newlines. More...

void	mpPrintTrim (const u32 *p, size_t ndigits)
	Print in hex but trim leading zero digits. More...

void	mpPrintTrimNL (const u32 *p, size_t ndigits)
	Print in hex, trim leading zeroes, add newlines. More...

size_t	mpConvFromOctets (u32 a[], size_t ndigits, const unsigned char *c, size_t nbytes)
	Converts nbytes octets into big digit a of max size ndigits. More...

size_t	mpConvToOctets (const u32 a[], size_t ndigits, unsigned char *c, size_t nbytes)
	Converts big digit a into string of octets, in big-endian order, padding to nbytes or truncating if necessary. More...

int	mpIsNegative (const u32 x[], size_t ndigits)
	Returns true (1) if x < 0, else false (0) More...

int	mpChs (u32 x[], const u32 y[], size_t ndigits)
	Sets x = -y. More...

int	mpAbs (u32 x[], const u32 y[], size_t ndigits)
	Sets x = \|y\|, the absolute value of y. More...

int	mpVersion (void)
	Returns version number = major1000+minor100+release*10+PP_OPTIONS. More...

Typedef Documentation

typedef uint32_t DIGIT_T

The basic BigDigit element, an unsigned 32-bit integer.

Function Documentation

int mpAbs	(	u32	x[],
		const u32	y[],
		size_t	ndigits
	)

Sets x = |y|, the absolute value of y.

Remarks: Expects a negative number to be stored in two's-complement representation.

Sets x = |y|, the absolute value of y.

References mpChs(), mpIsNegative(), and mpSetEqual().

u32 mpAdd	(	u32	w[],
		const u32	u[],
		const u32	v[],
		size_t	ndigits
	)

Computes w = u + v, returns carry.

Referenced by mpCubeRoot(), mpDivide(), mpModInv(), and mpSqrt().

void mpAndBits	(	u32	a[],
		const u32	b[],
		const u32	c[],
		size_t	ndigits
	)

Computes bitwise a = b AND c.

size_t mpBitLength	(	const u32	a[],
		size_t	ndigits
	)

Returns number of significant bits in a.

References mpSizeof().

Referenced by mpConvToOctets().

int mpChs	(	u32	x[],
		const u32	y[],
		size_t	ndigits
	)

Sets x = -y.

Remarks: Expects a negative number to be stored in two's-complement representation.

References mpIsNegative(), mpNotBits(), mpShortAdd(), and mpShortSub().

Referenced by mpAbs().

int mpCompare	(	const u32	a[],
		const u32	b[],
		size_t	ndigits
	)

Returns sign of (a-b) as {-1,0,+1} using constant-time algorithm.

Remarks: Constant-time with respect to ndigits

Returns sign of (a-b) as {-1,0,+1} using constant-time algorithm.

Referenced by mpCubeRoot(), mpDivide(), mpGcd(), mpRabinMiller(), and mpSqrt().

int mpCompare_q	(	const u32	a[],
		const u32	b[],
		size_t	ndigits
	)

Returns sign of (a-b) as {-1,0,+1} (quick)

Remarks: Not constant-time.

Returns sign of (a-b) as {-1,0,+1} (quick)

Not constant-time.

size_t mpConvFromOctets	(	u32	a[],
		size_t	ndigits,
		const unsigned char *	c,
		size_t	nbytes
	)

Converts nbytes octets into big digit a of max size ndigits.

Returns: actual number of digits set

References mpSetZero().

size_t mpConvToOctets	(	const u32	a[],
		size_t	ndigits,
		unsigned char *	c,
		size_t	nbytes
	)

Converts big digit a into string of octets, in big-endian order, padding to nbytes or truncating if necessary.

Returns: number of non-zero octets required.

References mpBitLength().

int mpCubeRoot	(	u32	s[],
		const u32	x[],
		size_t	ndigits
	)

Computes integer cube root s = floor(cuberoot(x))

References mpAdd(), mpCompare(), mpDivide(), mpSetEqual(), mpShortCmp(), and mpShortDiv().

int mpDivide	(	u32	q[],
		u32	r[],
		const u32	u[],
		size_t	udigits,
		u32	v[],
		size_t	vdigits
	)

Computes integer division of u by v such that u=qv+r.

Parameters

[out]	q	to receive quotient = u div v, an array of size `udigits`
[out]	r	to receive divisor = u mod v, an array of size `udigits`
[in]	u	dividend of size `udigits`
[in]	udigits	size of arrays `q` `r` and `u`
[in]	v	divisor of size `vdigits`
[in]	vdigits	size of array `v`

Warning: Trashes q and r first

References mpAdd(), mpCompare(), mpSetDigit(), mpSetEqual(), mpSetZero(), mpShiftLeft(), mpShiftRight(), mpShortDiv(), mpSizeof(), and spDivide().

Referenced by mpCubeRoot(), mpModInv(), mpModulo(), and mpSqrt().

int mpEqual	(	const u32	a[],
		const u32	b[],
		size_t	ndigits
	)

Returns true if a == b, else false, using constant-time algorithm.

Remarks: Constant-time with respect to ndigits

Returns true if a == b, else false, using constant-time algorithm.

int mpEqual_q	(	const u32	a[],
		const u32	b[],
		size_t	ndigits
	)

Returns true if a == b, else false (quick)

Remarks: Not constant-time.

Returns true if a == b, else false (quick)

Not constant-time.

int mpGcd	(	u32	g[],
		const u32	x[],
		const u32	y[],
		size_t	ndigits
	)

Computes g = gcd(x, y), the greatest common divisor of x and y.

References mpCompare(), mpIsZero(), mpModulo(), mpSetEqual(), mpShiftLeft(), mpShiftRight(), and mpSubtract().

int mpGetBit	(	u32	a[],
		size_t	ndigits,
		size_t	n
	)

Returns value 1 or 0 of bit n (0..nbits-1)

int mpIsNegative	(	const u32	x[],
		size_t	ndigits
	)

Returns true (1) if x < 0, else false (0)

Remarks: Expects a negative number to be stored in two's-complement representation.

Returns true (1) if x < 0, else false (0)

Referenced by mpAbs(), and mpChs().

int mpIsPrime	(	u32	w[],
		size_t	ndigits,
		size_t	t
	)

Returns true (1) if w is probably prime.

Parameters

[in]	w	Number to test
[in]	ndigits	size of array `w`
[in]	t	The count of Rabin-Miller primality tests to carry out (recommended at least 80)

Returns: true (1) if w is probably prime otherwise false (0)

Remarks: Uses FIPS-186-2/Rabin-Miller with trial division by small primes, which is faster in most cases than mpRabinMiller().

See Also: mpRabinMiller().

References mpRabinMiller(), mpShortCmp(), and mpShortMod().

int mpIsZero	(	const u32	a[],
		size_t	ndigits
	)

Returns true if a is zero, else false, using constant-time algorithm.

Remarks: Constant-time with respect to ndigits

Returns true if a is zero, else false, using constant-time algorithm.

Referenced by mpGcd(), mpJacobi(), mpModInv(), and mpRabinMiller().

int mpIsZero_q	(	const u32	a[],
		size_t	ndigits
	)

Returns true if a is zero, else false (quick)

Remarks: Not constant-time.

Returns true if a is zero, else false (quick)

Not constant-time.

int mpJacobi	(	const u32	a[],
		const u32	n[],
		size_t	ndigits
	)

Returns the Jacobi symbol (a/n) in {-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

References mpIsZero(), mpModulo(), mpSetEqual(), mpShiftRight(), mpShortCmp(), and mpShortMod().

int mpModExp	(	u32	y[],
		const u32	x[],
		const u32	e[],
		u32	m[],
		size_t	ndigits
	)

Computes y = x^e mod m.

Referenced by mpRabinMiller().

int mpModExp_ct	(	u32	yout[],
		const u32	x[],
		const u32	e[],
		u32	m[],
		size_t	ndigits
	)

Computes y = x^e mod m in constant time.

Remarks: Resistant to simple power analysis attack on private exponent. Slower than mpModExp().

Computes y = x^e mod m in constant time.

References mpSetDigit(), mpSetEqual(), and mpSizeof().

int mpModInv	(	u32	inv[],
		const u32	u[],
		const u32	m[],
		size_t	ndigits
	)

Computes the inverse of u modulo m, inv = u^{-1} mod m.

References mpAdd(), mpDivide(), mpIsZero(), mpMultiply(), mpSetDigit(), mpSetEqual(), mpSetZero(), mpShortCmp(), and mpSubtract().

int mpModMult	(	u32	a[],
		const u32	x[],
		const u32	y[],
		u32	m[],
		size_t	ndigits
	)

Computes a = (x * y) mod m.

References mpModulo(), and mpMultiply().

Referenced by mpRabinMiller().

void mpModPowerOf2	(	u32	a[],
		size_t	ndigits,
		size_t	L
	)

Computes a = a mod 2^L, ie clears all bits greater than L.

int mpModulo	(	u32	r[],
		const u32	u[],
		size_t	udigits,
		u32	v[],
		size_t	vdigits
	)

Computes remainder r = u mod v.

Parameters

[out]	r	to receive divisor = u mod v, an array of size `vdigits`
[in]	u	dividend of size `udigits`
[in]	udigits	size of arrays `r` and `u`
[in]	v	divisor of size `vdigits`
[in]	vdigits	size of array `v`

Remarks: Note that r is vdigits long here, but is udigits long in mpDivide().

References mpDivide(), and mpSetEqual().

Referenced by mpGcd(), mpJacobi(), and mpModMult().

int mpMultiply	(	u32	w[],
		const u32	u[],
		const u32	v[],
		size_t	ndigits
	)

Computes product w = u * v.

Parameters

[out]	w	To receive the product, an array of size 2 x `ndigits`
[in]	u	An array of size `ndigits`
[in]	v	An array of size `ndigits`
[in]	ndigits	size of arrays `u` and `v`

Warning: The product must be of size 2 x ndigits

References spMultiply().

Referenced by mpModInv(), and mpModMult().

void mpNotBits	(	u32	a[],
		const u32	b[],
		size_t	ndigits
	)

Computes bitwise a = NOT b.

Referenced by mpChs().

void mpOrBits	(	u32	a[],
		const u32	b[],
		const u32	c[],
		size_t	ndigits
	)

Computes bitwise a = b OR c.

void mpPrint	(	const u32 *	p,
		size_t	ndigits
	)

Print in decimal format with optional prefix and suffix strings.

Print all digits in hex incl leading zero digits

Referenced by mpPrintTrim().

void mpPrintHex	(	const char *	prefix,
		const u32 *	p,
		size_t	ndigits,
		const char *	suffix
	)

Print in hex format with optional prefix and suffix strings.

void mpPrintNL	(	const u32 *	p,
		size_t	ndigits
	)

Print all digits in hex with newlines.

Referenced by mpPrintTrimNL().

void mpPrintTrim	(	const u32 *	p,
		size_t	ndigits
	)

Print in hex but trim leading zero digits.

References mpPrint().

void mpPrintTrimNL	(	const u32 *	p,
		size_t	ndigits
	)

Print in hex, trim leading zeroes, add newlines.

References mpPrintNL().

size_t mpQuickRandBits	(	u32	a[],
		size_t	ndigits,
		size_t	nbits
	)

Generate a quick-and-dirty random mp number a of bit length at most nbits using plain-old-rand.

Remarks: Not crypto secure.

See Also: mpRandomBits()

Generate a quick-and-dirty random mp number a of bit length at most nbits using plain-old-rand.

References mpSetZero(), and spSimpleRand().

int mpRabinMiller	(	u32	w[],
		size_t	ndigits,
		size_t	t
	)

Returns true (1) if w is probably prime using just the Rabin-Miller test.

See Also: mpIsPrime() is preferred.

References mpCompare(), mpIsZero(), mpModExp(), mpModMult(), mpSetEqual(), mpSetZero(), mpShiftRight(), mpShortAdd(), mpShortCmp(), mpShortSub(), and mpSizeof().

Referenced by mpIsPrime().

int mpSetBit	(	u32	a[],
		size_t	ndigits,
		size_t	n,
		int	value
	)

Sets bit n of a (0..nbits-1) with value 1 or 0.

void mpSetDigit	(	u32	a[],
		u32	d,
		size_t	ndigits
	)

Sets a = d where d is a single digit.

Referenced by mpDivide(), mpModExp_ct(), and mpModInv().

void mpSetEqual	(	u32	a[],
		const u32	b[],
		size_t	ndigits
	)

Sets a = b.

Referenced by mpAbs(), mpCubeRoot(), mpDivide(), mpGcd(), mpJacobi(), mpModExp_ct(), mpModInv(), mpModulo(), mpRabinMiller(), and mpSqrt().

u32 mpSetZero	(	u32	a[],
		size_t	ndigits
	)

Sets a = 0.

Referenced by mpConvFromOctets(), mpDivide(), mpModInv(), mpQuickRandBits(), and mpRabinMiller().

u32 mpShiftLeft	(	u32	a[],
		const u32	b[],
		size_t	x,
		size_t	ndigits
	)

Computes a = b << x.

Referenced by mpDivide(), mpGcd(), and mpShortDiv().

u32 mpShiftRight	(	u32	a[],
		const u32	b[],
		size_t	x,
		size_t	ndigits
	)

Computes a = b >> x.

Referenced by mpDivide(), mpGcd(), mpJacobi(), mpRabinMiller(), and mpSqrt().

u32 mpShortAdd	(	u32	w[],
		const u32	u[],
		u32	d,
		size_t	ndigits
	)

Computes w = u + d, returns carry.

Referenced by mpChs(), and mpRabinMiller().

int mpShortCmp	(	const u32	a[],
		u32	d,
		size_t	ndigits
	)

Returns sign of (a - d) where d is a single digit.

Referenced by mpCubeRoot(), mpIsPrime(), mpJacobi(), mpModInv(), mpRabinMiller(), and mpSqrt().

u32 mpShortDiv	(	u32	q[],
		const u32	u[],
		u32	d,
		size_t	ndigits
	)

Computes quotient q = u div d, returns remainder.

References mpShiftLeft(), and spDivide().

Referenced by mpCubeRoot(), mpDivide(), and mpShortMod().

u32 mpShortMod	(	const u32	a[],
		u32	d,
		size_t	ndigits
	)

Computes remainder r = a mod d.

References mpShortDiv().

Referenced by mpIsPrime(), and mpJacobi().

u32 mpShortMult	(	u32	p[],
		const u32	x[],
		u32	d,
		size_t	ndigits
	)

Computes product p = x * d.

References spMultiply().

u32 mpShortSub	(	u32	w[],
		const u32	u[],
		u32	d,
		size_t	ndigits
	)

Computes w = u - d, returns borrow.

Referenced by mpChs(), and mpRabinMiller().

size_t mpSizeof	(	const u32	a[],
		size_t	ndigits
	)

Returns number of significant non-zero digits in a.

Referenced by mpBitLength(), mpDivide(), mpModExp_ct(), and mpRabinMiller().

int mpSqrt	(	u32	s[],
		const u32	x[],
		size_t	ndigits
	)

Computes integer square root s = floor(sqrt(x))

References mpAdd(), mpCompare(), mpDivide(), mpSetEqual(), mpShiftRight(), and mpShortCmp().

int mpSquare	(	u32	w[],
		const u32	x[],
		size_t	ndigits
	)

Computes square w = x^2.

Parameters

[out]	w	array of size 2 x `ndigits` to receive square
[in]	x	array of size `ndigits`
[in]	ndigits	size of array `x`

Warning: The product w must be of size 2 x ndigits

References spMultiply().

u32 mpSubtract	(	u32	w[],
		const u32	u[],
		const u32	v[],
		size_t	ndigits
	)

Computes w = u - v, returns borrow.

Referenced by mpGcd(), and mpModInv().

int mpVersion ( void )

Returns version number = major*1000+minor*100+release*10+PP_OPTIONS.

void mpXorBits	(	u32	a[],
		const u32	b[],
		const u32	c[],
		size_t	ndigits
	)

Computes bitwise a = b XOR c.

u32 spDivide	(	u32 *	q,
		u32 *	r,
		const u32	u[2],
		u32	v
	)

Computes quotient q = u div v, remainder r = u mod v, where q, r and v are single digits.

Referenced by mpDivide(), and mpShortDiv().

int spMultiply	(	u32	p[2],
		u32	x,
		u32	y
	)

Computes p = x * y, where x and y are single digits.

Referenced by mpMultiply(), mpShortMult(), and mpSquare().

u32 spSimpleRand	(	u32	lower,
		u32	upper
	)

Returns a simple pseudo-random digit between lower and upper.

Remarks: Not crypto secure.

See Also: spBetterRand()

Referenced by mpQuickRandBits().

Overview

Typedefs

Functions

Typedef Documentation

Function Documentation