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

Determine whether

nis prime. Return 2 ifnis definitely prime, return 1 ifnis probably prime (without being certain), or return 0 ifnis definitely composite.This function does some trial divisions, then some Miller-Rabin probabilistic primality tests. The argument

repscontrols how many such tests are done; a higher value will reduce the chances of a composite being returned as “probably prime”. 25 is a reasonable number; a composite number will then be identified as a prime with a probability of less than 2^(-50).Miller-Rabin and similar tests can be more properly called compositeness tests. Numbers which fail are known to be composite but those which pass might be prime or might be composite. Only a few composites pass, hence those which pass are considered probably prime.

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

Set

ropto the next prime greater thanop.This function uses 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

ropto the greatest common divisor ofop1andop2. 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

op1andop2. Ifropis 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 argumentop1. Note that the result will always fit ifop2is non-zero.

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

Set

gto the greatest common divisor ofaandb, and in addition setsandtto coefficients satisfyinga*s+b*t=g. The value ingis always positive, even if one or both ofaandbare negative (or zero if both inputs are zero). The values insandtare chosen such that normally, abs(s) < abs(b) / (2g) and abs(t) < abs(a) / (2g), and these relations definesandtuniquely. There are a few exceptional cases:If abs(

a) = abs(b), thens= 0,t= sgn(b).Otherwise,

s= sgn(a) ifb= 0 or abs(b) = 2g, andt= sgn(b) ifa= 0 or abs(a) = 2g.In all cases,

s= 0 if and only ifg= abs(b), i.e., ifbdividesaora=b= 0.If

tis`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`)

— Function: void

Set

ropto the least common multiple ofop1andop2.ropis always positive, irrespective of the signs ofop1andop2.ropwill be zero if eitherop1orop2is zero.

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

Compute the inverse of

op1moduloop2and put the result inrop. If the inverse exists, the return value is non-zero andropwill satisfy 0 <rop< abs(op2). If an inverse doesn't exist the return value is zero andropis undefined. The behaviour of this function is undefined whenop2is zero.

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

Calculate the Jacobi symbol (

a/b). This is defined only forbodd.

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

Calculate the Legendre symbol (

a/p). This is defined only forpan odd positive prime, and for suchpit'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`)

— Function: int

— Function: int

— Function: int

— Function: int

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

bis 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.cwhich 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

ffromopand store the result inrop. 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`)

— Function: void

— Function: void

Set

ropto the factorial ofn:`mpz_fac_ui`

computes the plain factorialn!,`mpz_2fac_ui`

computes the double-factorialn!!, and`mpz_mfac_uiui`

them-multi-factorialn!^(m).

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

Set

ropto the primorial ofn, 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`)

— Function: void

Compute the binomial coefficient

noverkand store the result inrop. Negative values ofnare 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`)

— Function: void

`mpz_fib_ui`

setsfnto to F[n], then'th Fibonacci number.`mpz_fib2_ui`

setsfnto F[n], andfnsub1to 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`)

— Function: void

`mpz_lucnum_ui`

setslnto to L[n], then'th Lucas number.`mpz_lucnum2_ui`

setslnto L[n], andlnsub1to 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 Algorithm, the reverse is straightforward too.