Next: Integer Comparisons, Previous: Integer Roots, Up: Integer Functions [Index]

- 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^(-*. Reasonable values of`reps`)`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`.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

`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. The value in`a`*`s`+`b`*`t`=`g``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(*and`s`) < abs(`b`) / (2`g`)*abs(*, and these relations define`t`) < abs(`a`) / (2`g`)`s`and`t`uniquely. There are a few exceptional cases:If

*abs(*, then`a`) = abs(`b`),`s`= 0.`t`= sgn(`b`)Otherwise,

if`s`= sgn(`a`)or`b`= 0*abs(*, and`b`) = 2`g`if`t`= sgn(`b`)or`a`= 0*abs(*.`a`) = 2`g`In all cases,

if and only if`s`= 0, i.e., if`g`= abs(`b`)`b`divides`a`or.`a`=`b`= 0If

`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 <=*(with`rop`< abs(`op2`)possible only when`rop`= 0*abs(*, i.e., in the somewhat degenerate zero ring). If an inverse doesn’t exist the return value is zero and`op2`) = 1`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

*(*. This is defined only for`a`/`b`)`b`odd.

- Function:
*int***mpz_legendre***(const mpz_t*`a`, const mpz_t`p`) -
Calculate the Legendre symbol

*(*. This is defined only for`a`/`p`)`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

*(*with the Kronecker extension`a`/`b`)*(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

and store the result in`n`over`k``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 to*F[n]*, the`n`’th 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 to*L[n]*, the`n`’th 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 Algorithm, the reverse is straightforward too.

Next: Integer Comparisons, Previous: Integer Roots, Up: Integer Functions [Index]