14.2 Number Theory

Team-Fly

In contrast to the arithmetic functions, the following number-theoretic member functions do not overwrite the implicit first argument with the result. The reason for this is that with more complex functions it has been shown in practice not to be practical to overwrite, as is the case with simple arithmetic functions. The results of the following functions are thus returned as values rather than as pointers.

Function:	calculate the greatest integer less than or equal to the base-2 logarithm of a LINT object
Syntax:	const unsigned int LINT::ld (void);
Input:	implicit argument a
Return:	integer part of the base-2 logarithm of a
Example:	i = a.ld ();

Function:	calculate the greatest common divisor of two LINT objects
Syntax:	const LINT LINT::gcd (const LINT& b);
Input:	implicit argument a second argument b
Return:	gcd (a, b) of the input values
Example:	c = a.gcd (b);

Function:	calculate the multiplicative inverse modulo n
Syntax:	const LINT LINT::inv (const LINT& n);
Input:	implicit argument a modulus n
Return:	multiplicative inverse of a modulo n (if the result is equal to zero, then gcd(a, n) > 1 and the inverse does not exist)
Example:	c = a.inv (n);

Function:	calculate the greatest common divisor of a and b as well as its representation g = ua+vb as a linear combination of a and b
Syntax:	const LINT LINT::xgcd(const LINT& b, LINT& u, int& sign_u, LINT& v, int& sign_v);
Input:	implicit argument a, second argument b
Output:	Factor u of the representation of gcd (a, b) sign of u in sign_u factor v of the representation of gcd (a, b) sign of v in sign_v
Return:	gcd(a, b) of the input values
Example:	g = a.xgcd (b, u, sign_u, v, sign_v);

Function:	calculate the least common multiple (lcm) of two LINT objects
Syntax:	const LINT LINT::lcm(const LINT& b);
Input:	implicit argument a factor b
Return:	lcm(a, b) of the input values
Example:	c = a.lcm (b);

Function:	solution of a system of linear congruences x ≡ a mod m, x ≡ b mod n,
Syntax:	const LINT LINT::chinrem(const LINT& m, const LINT& b, const LINT& n);
Input:	implicit argument a, modulus m, argument b, modulus n
Return:	solution x of the congruence system if all is ok (Get_Warning_Status() == E_LINT_ERR indicates that an overflow has occurred or that the congruences have no common solution)
Example:	x = a.chinrem (m, b, n);

The friend function chinrem(const int noofeq, LINT** coeff) accepts a vector coeff of pointers to LINT objects, which are passed as coefficients a₁, m₁, a₂, m₂, a₃, m₃,... of a system of linear congruences with "arbitrarily" many equations x ≡ a_i mod m_i, i = 1,..., noofeq (see Appendix B).

Function:	calculation of the Jacobi symbol of two LINT objects
Syntax:	const int LINT::jacobi (const LINT& b);
Input:	implicit argument a, second argument b
Return:	Jacobi symbol of the input values
Example:	i = a.jacobi (b);

Function:	calculation of the integer part of the square root of a LINT object
Syntax:	const LINT LINT::root (void);
Input:	implicit argument a
Return:	integer part of the square root of the input value
Example:	c = a.root ();

Function:	calculation of the square root modulo a prime p of a LINT object
Syntax:	const LINT LINT::root (const LINT& p);
Input:	implicit argument a, prime modulus p > 2
Return:	square root of a if a is a quadratic residue modulo p otherwise 0 (Get_Warning_Status() == E_LINT_ERR indicates that a is not a quadratic residue modulo p)
Example:	c = a.root (p);

Function:	calculation of the square root of a LINT object modulo a prime product p·q
Syntax:	const LINT LINT::root (const LINT& p, const LINT& q);
Input:	implicit argument a prime modulus p > 2, prime modulus q > 2
Return:	square root of a if a is a quadratic residue modulo pq otherwise 0 (Get_Warning_Status() == E_LINT_ERR indicates that a is not a quadratic residue modulo p*q)
Example:	c = a.root (p, q);

Function:	test of whether a LINT object is a square
Syntax:	const int LINT::issqr(void);,
Input:	test candidate a as implicit argument
Return:	square root of a if a is a square otherwise 0 if a == 0 or a not a square
Example:	if(0 == (r = a.issqr ())) // ...

Function:	probabilistic primality test of a LINT object
Syntax:	const int LINT::isprime (void);
Input:	test candidate a as implicit argument
Return:	1 if a is a "probable" prime 0 otherwise
Example:	if(a.isprime ()) // ...

Function:	calculate the two-part of a LINT object
Syntax:	const int LINT::twofact (LINT& b);
Input:	implicit argument a
Output:	b (odd part of a)
Return:	exponent of the odd part of a
Example:	e = a.twofact (b);

Team-Fly