[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

## 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 composite.This function does some trial divisions, then some Miller-Rabin probabilistic primality tests. The argument

`reps`controls 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

`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`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 <*. If an inverse doesn’t exist the return value is zero and`rop`< abs(`op2`)`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 section 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, the reverse is straightforward too.

[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

This document was generated on *March 31, 2014* using *texi2html 5.0*.