numtheory Namespace Reference

number theoretic concepts More...

Classes
class	Clucas_capsule
Functions
bool	strong_probab_prime (const unsigned int p, const unsigned int base)
bool	probab_prime (const unsigned int p)
bool	is_prime (register const int p)
signed int	jacobi (int a, unsigned int b)
signed int	legendre (signed int a, const unsigned int p)
unsigned int	invmod (const unsigned int x, const unsigned int m)
unsigned int	bininvmod (register unsigned int x, register const unsigned int m)
static const char shifts[64]	__attribute__ ((aligned(64)))
unsigned int	montgominvmod (register unsigned int x, unsigned int m)
unsigned int	normalized_signed_mod (const signed int x, const int m)
unsigned int	reciprocal (register const unsigned int m)
unsigned int	normalized_signed_mod (register const signed int x, register const int m, const int &recip_m)
unsigned int	mulmod (const unsigned int a, const unsigned int b, const unsigned int m)
unsigned int	squaremod (const unsigned int a, const unsigned int m)
unsigned int	normalized_signed_mulmod (signed int x1, signed int x2, const int m)
unsigned int	powmod (register unsigned int a, register unsigned int pow, const unsigned int m)
unsigned int	gcd (register unsigned int a, register unsigned int b)
unsigned short int	gcd (register unsigned short int a, register unsigned short int b)
unsigned int	oddgcd (register unsigned int a, register unsigned int b)
bool	coprime (register unsigned int a, register unsigned int b)
unsigned int	fastinvmod (const unsigned int x, const unsigned int m)
unsigned int	fastinvmod_23bit (const unsigned int x, const unsigned int m)
unsigned int	sqrtmod (const unsigned int Radikant, const unsigned int Primzahl)

---

Detailed Description

number theoretic concepts

---

Function Documentation

static const char shifts [64] numtheory::__attribute__

(

(aligned(64))

)

[static]

unsigned int numtheory::bininvmod	(	register unsigned int	x,
		register const unsigned int	m
	)

Parameters:

	x	an odd unsigned integer value
	m	an unsigned integer value

Returns:

the modular inverse of x mod m

Remarks:

• Let y be the modular inverse of x mod m, then x * y = 1 (mod m)
• The result is only defined, if x and m are coprime, 0 < x < m and m is odd.
• x>m for x =x'*2^k and 0 < x' < m is also allowed

Parameters:

	x	an odd unsigned integer value
	m	an unsigned integer value

Returns:

the modular inverse of x mod m

Remarks:

• Let y be the modular inverse of x mod m, then x * y = 1 (mod m)
• The result is only defined, if x and m are coprime, 0 < x < m and m is odd.

Definition at line 357 of file modulo.cc.

Referenced by main().

bool numtheory::coprime	(	register unsigned int	a,
		register unsigned int	b
	)			[inline]

Parameters:

	a	an unsigned integer
	b	an unsigned integer

Returns:

whether a and b are coprime (that is gcd(a,b)==1)

Definition at line 584 of file modulo.H.

Referenced by CmpqsPolynom::compute_next_polynomial(), and main().

unsigned int numtheory::fastinvmod	(	const unsigned int	x,
		const unsigned int	m
	)			[inline]

Parameters:

	x	an odd unsigned integer value
	m	an unsigned integer value

Returns:

the modular inverse of x mod m

Remarks:

• this is an inline function so that you can choose the most performant algorithm
• Let y be the modular inverse of x mod m, then x * y = 1 (mod m)
• The result is only defined, if x and m are coprime, 0 < x < m and m is odd.
• this is an inline function so that you can choose the most performant implementation without changing the source code.

Definition at line 660 of file modulo.H.

Referenced by DynamicFactorArrays::compute_Deltas_for_DynamicFactors(), and numtheory::Clucas_capsule::lucas().

unsigned int numtheory::fastinvmod_23bit	(	const unsigned int	x,
		const unsigned int	m
	)			[inline]

Definition at line 691 of file modulo.H.

References fast_invmod().

Here is the call graph for this function:

unsigned short int numtheory::gcd	(	register unsigned short int	a,
		register unsigned short int	b
	)			[inline]

Definition at line 516 of file modulo.H.

Referenced by elliptic_curves::go(), and polphi_template().

unsigned int numtheory::gcd	(	register unsigned int	a,
		register unsigned int	b
	)			[inline]

Returns:

greatest common divisor of a and b

Definition at line 509 of file modulo.H.

Referenced by elliptic_curves::go(), and polphi_template().

unsigned int numtheory::invmod	(	const unsigned int	x,
		const unsigned int	m
	)

Parameters:

	x	an unsigned integer value
	m	an unsigned integer value

Returns:

the modular inverse of x mod m

Remarks:

• Let y be the modular inverse of x mod m, then x * y = 1 (mod m)
• The result is only defined, if x and m are coprime.

Definition at line 184 of file modulo.cc.

References std::cerr, std::endl(), exit(), and mulmod().

Referenced by StaticFactorbase::compute_StaticFactorbase(), main(), and test01().

Here is the call graph for this function:

bool numtheory::is_prime

(

register const int

p

)

Parameters:

p

unsigned integer to check for primality

Returns:

whether p is a prime number

Remarks:

This function is slow for large numbers, but safe for all numbers, since it is based on trial division.

Definition at line 84 of file modulo.cc.

Referenced by StaticFactorbase::compute_StaticFactorbase(), determine_best_MPQS_Multiplier(), polynomial::CDFT_base::get_valid_primes_for(), elliptic_curves::go(), legendre(), and polphi_template().

signed int numtheory::jacobi	(	int	a,
		unsigned int	b
	)

Parameters:

	a	an integer value
	b	an odd unsigned integer value

Returns:

Jacobi symbol (a/b) (which is undefined for even b)

Definition at line 106 of file modulo.cc.

Referenced by legendre().

signed int numtheory::legendre	(	signed int	a,
		const unsigned int	p
	)

Parameters:

	a	an integer value
	p	an odd prime number (as unsigned integer)

Returns:

Legendre symbol (a/p), which is

• 1, if a is a quadratic residue modulo p
• -1, if a is not a quadratic residue modulo p
• 0, if a and p are not coprime

Remarks:

• The result is only defined, if p is an odd prime number. You cannot rely on on any specific behaviour on this function, if this condition is not met!
• For valid values the result is identical to that of the jacobi function.

Definition at line 151 of file modulo.cc.

References cerr, endl(), exit(), is_prime(), and jacobi().

Referenced by numtheory::Clucas_capsule::lucas().

Here is the call graph for this function:

unsigned int numtheory::montgominvmod	(	register unsigned int	x,
		unsigned int	m
	)

Parameters:

	x	an unsigned integer value
	m	an unsigned integer value

Returns:

the modular inverse of x mod m

Remarks:

• Let y be the modular inverse of x mod m, then x * y = 1 (mod m)
• The result is only defined, if x and m are coprime, 0 < x < m and m is odd.

Parameters:

	x	an odd unsigned integer value
	m	an unsigned integer value

Returns:

the modular inverse of x mod m

Remarks:

• Let y be the modular inverse of x mod m, then x * y = 1 (mod m)
• The result is only defined, if x and m are coprime, 0 < x < m and m is odd.

Definition at line 520 of file modulo.cc.

Referenced by main().

unsigned int numtheory::mulmod	(	const unsigned int	a,
		const unsigned int	b,
		const unsigned int	m
	)			[inline]

Parameters:

	a	an unsigned integer value
	b	an unsigned integer value
	m	an unsigned integer value

Returns:

a * b mod m

Remarks:

• This function is often necessary to avoid integer overflows in the product.
• i386 architecture specific
• for generic usage you should assure a < m and b < m

Definition at line 249 of file modulo.H.

Referenced by DynamicFactorArrays::compute_Deltas_for_DynamicFactors(), StaticFactorbase::compute_StaticFactorbase(), invmod(), numtheory::Clucas_capsule::lucas(), numtheory::Clucas_capsule::lucasv(), main(), and sqrtmod().

unsigned int numtheory::normalized_signed_mod	(	register const signed int	x,
		register const int	m,
		const int &	recip_m
	)			[inline]

Parameters:

	x	a signed integer value
	m	an unsigned 32bit integer value
	recip_m	the reciprocal of m (2^32/m +1)

Returns:

x mod m

Remarks:

This function is a replacement for x % m. It normalizes the result to a nonnegative number. (On most architectures x % m is negative, if x is negative.) Since a precomputed reciprocal is used, this implementation trades one expensive integer division for two cheap integer multiplications.

Definition at line 131 of file modulo.H.

Referenced by DynamicFactorArrays::compute_Deltas_for_DynamicFactors(), and main().

unsigned int numtheory::normalized_signed_mod	(	const signed int	x,
		const int	m
	)			[inline]

Parameters:

	x	a signed integer value
	m	an unsigned integer value

Returns:

x mod m

Remarks:

This function is a replacement for x % m. It normalizes the result to a nonnegative number. (On most architectures x % m is negative, if x is negative.)

Definition at line 42 of file modulo.H.

References polynomial::mod().

Here is the call graph for this function:

unsigned int numtheory::normalized_signed_mulmod	(	signed int	x1,
		signed int	x2,
		const int	m
	)			[inline]

Parameters:

	x1	a signed integer value
	x2	a signed integer value
	m	an unsigned integer value

Returns:

x1 * x2 mod m

Remarks:

This function computes the normalized reduced product (a nonnegative number).

Definition at line 352 of file modulo.H.

unsigned int numtheory::oddgcd	(	register unsigned int	a,
		register unsigned int	b
	)			[inline]

Parameters:

	a	must be an odd unsigned integer
	b	must be an odd unsigned integer

Returns:

greatest common divisor of a and b

Remarks:

• This function should be somewhat faster than the normal gcd computation since divisions are replaced by shift operations.

• If the algorithm is fed with even values, it returns the odd part of their gcd.

Definition at line 533 of file modulo.H.

Referenced by main().

unsigned int numtheory::powmod	(	register unsigned int	a,
		register unsigned int	pow,
		const unsigned int	m
	)			[inline]

modular exponentiation

Parameters:

	a	base, an unsigned integer value
	pow	exponent, an unsigned integer value
	m	unsigned integer value

Returns:

a ^ pow mod m

Definition at line 421 of file modulo.H.

Referenced by numtheory::Clucas_capsule::lucasv(), sqrtmod(), and strong_probab_prime().

bool numtheory::probab_prime

(

const unsigned int

p

)

Parameters:

p

unsigned integer to check for primality

Returns:

whether p is probably prime to the bases 2, 7 and 61.

Remarks:

actually the result returns, whether p is prime, iff 61 < p < 4.759.123.141 (and no integer overflow occurs), as someone has checked these conditions beforehand.

Definition at line 63 of file modulo.cc.

References strong_probab_prime().

Referenced by CmpqsFactor::DLP_get(), CmpqsFactor::DLP_get_using_pollard_rho(), test01(), and elliptic_curves::XZ_multiply().

Here is the call graph for this function:

unsigned int numtheory::reciprocal

(

register const unsigned int

m

)

[inline]

Parameters:

m

an unsigned 32bit integer value

Returns:

recip_m the reciprocal of m (=2^32/m +1)

Definition at line 98 of file modulo.H.

Referenced by StaticFactorbase::compute_StaticFactorbase().

unsigned int numtheory::sqrtmod	(	const unsigned int	Radikant,
		const unsigned int	Primenumber
	)

Parameters:

	Radikant	an unsigned integer value
	Primzahl	a prime unsigned integer value

Returns:

square root of Radikant mod Primzahl, that is an unsigned integer value r, such that r * r mod Primzahl = Radikant

Remarks:

• primality of Primzahl isn't checked
  • the result is undefined, if Primzahl is composite
  • you can check this beforehand using is_prime() or probab_prime()
• if no solution exists, the result is undefined
  • you can use legendre() to check, whether a solution exists

Parameters:

	Radikant	an unsigned integer value
	Primenumber	a prime unsigned integer value

Returns:

square root of Radikant mod Primenumber, that is an unsigned integer value r, such that r * r mod Primenumber = Radikant

Remarks:

• primality of Primenumber isn't checked
  • the result is undefined, if Primenumber is composite
  • you can check this beforehand using is_prime() or probab_prime()
• if no solution exists, the result is undefined
  • you can use legendre() to check, whether a solution exists

Definition at line 133 of file sqrt_modulo.cc.

References numtheory::Clucas_capsule::lucas(), mulmod(), powmod(), and squaremod().

Referenced by SQRT_kN_mod_PrimeNumber().

Here is the call graph for this function:

unsigned int numtheory::squaremod	(	const unsigned int	a,
		const unsigned int	m
	)			[inline]

Parameters:

	a	an unsigned integer value with a < m
	m	an unsigned integer value

Returns:

a * a mod m

Remarks:

• This function is often necessary to avoid integer overflows in the product, it should be slightly faster than the multiplication function.

• i386 architecture specific
• for generic usage you should assure a < m

Definition at line 283 of file modulo.H.

Referenced by DynamicFactorArrays::compute_Deltas_for_DynamicFactors(), StaticFactorbase::compute_StaticFactorbase(), CmpqsPolynom::get_A2_mod(), numtheory::Clucas_capsule::lucas(), numtheory::Clucas_capsule::lucasv(), sqrtmod(), and strong_probab_prime().

bool numtheory::strong_probab_prime	(	const unsigned int	p,
		const unsigned int	base
	)

Parameters:

	p	unsigned integer to test for primality
	base	base for the strong probable prime test

Returns:

whether p is a strong probable prime regarding to base .

Definition at line 39 of file modulo.cc.

References powmod(), and squaremod().

Referenced by probab_prime().

Here is the call graph for this function:

---