### 5.9 Number Theoretic Functions

Function: `int` mpz_probab_prime_p `(const mpz_t n, int reps)`

Determine whether n is prime. Return 2 if n is definitely prime, return 1 if n is probably prime (without being certain), or return 0 if n is definitely non-prime.

This function performs some trial divisions, a Baillie-PSW probable prime test, then reps-24 Miller-Rabin probabilistic primality tests. A higher reps value will reduce the chances of a non-prime being identified as “probably prime”. A composite number will be identified as a prime with an asymptotic probability of less than 4^(-reps). Reasonable values of reps are between 15 and 50.

GMP versions up to and including 6.1.2 did not use the Baillie-PSW primality test. In those older versions of GMP, this function performed reps Miller-Rabin tests.

Function: `void` mpz_nextprime `(mpz_t rop, const mpz_t op)`

Set rop to the next prime greater than op.

Function: `int` mpz_prevprime `(mpz_t rop, const mpz_t op)`

Set rop to the greatest prime less than op.

If a previous prime doesn’t exist (i.e. op < 3), rop is unchanged and 0 is returned.

Return 1 if rop is a probably prime, and 2 if rop is definitely prime.

These functions use a probabilistic algorithm to identify primes. For practical purposes it’s adequate, the chance of a composite passing will be extremely small.

Function: `void` mpz_gcd `(mpz_t rop, const mpz_t op1, const mpz_t op2)`

Set rop to the greatest common divisor of op1 and op2. The result is always positive even if one or both input operands are negative. Except if both inputs are zero; then this function defines gcd(0,0) = 0.

Function: `unsigned long int` mpz_gcd_ui `(mpz_t rop, const mpz_t op1, unsigned long int op2)`

Compute the greatest common divisor of op1 and op2. If rop is not `NULL`, store the result there.

If the result is small enough to fit in an `unsigned long int`, it is returned. If the result does not fit, 0 is returned, and the result is equal to the argument op1. Note that the result will always fit if op2 is non-zero.

Function: `void` mpz_gcdext `(mpz_t g, mpz_t s, mpz_t t, const mpz_t a, const mpz_t b)`

Set g to the greatest common divisor of a and b, and in addition set s and t to coefficients satisfying a*s + b*t = g. The value in g is always positive, even if one or both of a and b are negative (or zero if both inputs are zero). The values in s and t are chosen such that normally, abs(s) < abs(b) / (2 g) and abs(t) < abs(a) / (2 g), and these relations define s and t uniquely. There are a few exceptional cases:

If abs(a) = abs(b), then s = 0, t = sgn(b).

Otherwise, s = sgn(a) if b = 0 or abs(b) = 2 g, and t = sgn(b) if a = 0 or abs(a) = 2 g.

In all cases, s = 0 if and only if g = abs(b), i.e., if b divides a or a = b = 0.

If t or g is `NULL` then that value is not computed.

Function: `void` mpz_lcm `(mpz_t rop, const mpz_t op1, const mpz_t op2)`
Function: `void` mpz_lcm_ui `(mpz_t rop, const mpz_t op1, unsigned long op2)`

Set rop to the least common multiple of op1 and op2. rop is always positive, irrespective of the signs of op1 and op2. rop will be zero if either op1 or op2 is zero.

Function: `int` mpz_invert `(mpz_t rop, const mpz_t op1, const mpz_t op2)`

Compute the inverse of op1 modulo op2 and put the result in rop. If the inverse exists, the return value is non-zero and rop will satisfy 0 <= rop < abs(op2) (with rop = 0 possible only when abs(op2) = 1, i.e., in the somewhat degenerate zero ring). If an inverse doesn’t exist the return value is zero and rop is undefined. The behaviour of this function is undefined when op2 is zero.

Function: `int` mpz_jacobi `(const mpz_t a, const mpz_t b)`

Calculate the Jacobi symbol (a/b). This is defined only for b odd.

Function: `int` mpz_legendre `(const mpz_t a, const mpz_t p)`

Calculate the Legendre symbol (a/p). This is defined only for p an odd positive prime, and for such p it’s identical to the Jacobi symbol.

Function: `int` mpz_kronecker `(const mpz_t a, const mpz_t b)`
Function: `int` mpz_kronecker_si `(const mpz_t a, long b)`
Function: `int` mpz_kronecker_ui `(const mpz_t a, unsigned long b)`
Function: `int` mpz_si_kronecker `(long a, const mpz_t b)`
Function: `int` mpz_ui_kronecker `(unsigned long a, const mpz_t b)`

Calculate the Jacobi symbol (a/b) with the Kronecker extension (a/2)=(2/a) when a odd, or (a/2)=0 when a even.

When b is odd the Jacobi symbol and Kronecker symbol are identical, so `mpz_kronecker_ui` etc can be used for mixed precision Jacobi symbols too.

For more information see Henri Cohen section 1.4.2 (see References), or any number theory textbook. See also the example program demos/qcn.c which uses `mpz_kronecker_ui`.

Function: `mp_bitcnt_t` mpz_remove `(mpz_t rop, const mpz_t op, const mpz_t f)`

Remove all occurrences of the factor f from op and store the result in rop. The return value is how many such occurrences were removed.

Function: `void` mpz_fac_ui `(mpz_t rop, unsigned long int n)`
Function: `void` mpz_2fac_ui `(mpz_t rop, unsigned long int n)`
Function: `void` mpz_mfac_uiui `(mpz_t rop, unsigned long int n, unsigned long int m)`

Set rop to the factorial of n: `mpz_fac_ui` computes the plain factorial n!, `mpz_2fac_ui` computes the double-factorial n!!, and `mpz_mfac_uiui` the m-multi-factorial n!^(m).

Function: `void` mpz_primorial_ui `(mpz_t rop, unsigned long int n)`

Set rop to the primorial of n, i.e. the product of all positive prime numbers <=n.

Function: `void` mpz_bin_ui `(mpz_t rop, const mpz_t n, unsigned long int k)`
Function: `void` mpz_bin_uiui `(mpz_t rop, unsigned long int n, unsigned long int k)`

Compute the binomial coefficient n over k and store the result in rop. Negative values of n are supported by `mpz_bin_ui`, using the identity bin(-n,k) = (-1)^k * bin(n+k-1,k), see Knuth volume 1 section 1.2.6 part G.

Function: `void` mpz_fib_ui `(mpz_t fn, unsigned long int n)`
Function: `void` mpz_fib2_ui `(mpz_t fn, mpz_t fnsub1, unsigned long int n)`

`mpz_fib_ui` sets fn to F[n], the nth Fibonacci number. `mpz_fib2_ui` sets fn to F[n], and fnsub1 to F[n-1].

These functions are designed for calculating isolated Fibonacci numbers. When a sequence of values is wanted it’s best to start with `mpz_fib2_ui` and iterate the defining F[n+1]=F[n]+F[n-1] or similar.

Function: `void` mpz_lucnum_ui `(mpz_t ln, unsigned long int n)`
Function: `void` mpz_lucnum2_ui `(mpz_t ln, mpz_t lnsub1, unsigned long int n)`

`mpz_lucnum_ui` sets ln to L[n], the nth Lucas number. `mpz_lucnum2_ui` sets ln to L[n], and lnsub1 to L[n-1].

These functions are designed for calculating isolated Lucas numbers. When a sequence of values is wanted it’s best to start with `mpz_lucnum2_ui` and iterate the defining L[n+1]=L[n]+L[n-1] or similar.

The Fibonacci numbers and Lucas numbers are related sequences, so it’s never necessary to call both `mpz_fib2_ui` and `mpz_lucnum2_ui`. The formulas for going from Fibonacci to Lucas can be found in Lucas Numbers, the reverse is straightforward too.