Number Theoretic Functions

Function: int mpz_probab_prime_p (mpz_t n, int reps)

If this function returns 0, n is definitely not prime. If it returns 1, then n is `probably' prime. If it returns 2, then n is surely prime. Reasonable values of reps vary from 5 to 10; a higher value lowers the probability for a non-prime to pass as a `probable' prime.

The function uses Miller-Rabin's probabilistic test.

Function: int mpz_nextprime (mpz_t rop, mpz_t op)

Set rop to the next prime greater than op.

This function uses a probabilistic algorithm to identify primes, but for for practical purposes it's adequate, since the chance of a composite passing will be extremely small.

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

Set rop to the greatest common divisor of op1 and op2. The result is always positive even if either of or both input operands are negative.

Function: unsigned long int mpz_gcd_ui (mpz_t rop, 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, mpz_t a, mpz_t b)

Compute g, s, and t, such that as + bt = g = gcd(a, b). If t is NULL, that argument is not computed.

Function: void mpz_lcm (mpz_t rop, mpz_t op1, mpz_t op2)

Set rop to the least common multiple of op1 and op2.

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

Compute the inverse of op1 modulo op2 and put the result in rop. Return non-zero if an inverse exists, zero otherwise. When the function returns zero, rop is undefined.

Function: int mpz_jacobi (mpz_t op1, mpz_t op2)

Function: int mpz_legendre (mpz_t op1, mpz_t op2)

Compute the Jacobi and Legendre symbols, respectively. op2 should be odd and must be positive.

Function: int mpz_si_kronecker (long a, mpz_t b);

Function: int mpz_ui_kronecker (unsigned long a, mpz_t b);

Function: int mpz_kronecker_si (mpz_t a, long b);

Function: int mpz_kronecker_ui (mpz_t a, unsigned long b);

@ifnottex Calculate the value of the Kronecker/Jacobi symbol (a/b), with the Kronecker extension (a/2)=(2/a) when a odd, or (a/2)=0 when a even. All values of a and b give a well-defined result. See Henri Cohen, section 1.4.2, for more information (see section References). See also the example program `demos/qcn.c' which uses mpz_kronecker_ui.

Function: unsigned long int mpz_remove (mpz_t rop, mpz_t op, mpz_t f)

Remove all occurrences of the factor f from op and store the result in rop. Return the multiplicity of f in op.

Function: void mpz_fac_ui (mpz_t rop, unsigned long int op)

Set rop to op!, the factorial of op.

Function: void mpz_bin_ui (mpz_t rop, 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 @ifnottex n over k and store the result in rop. Negative values of n are supported by mpz_bin_ui, using the identity @ifnottex 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 rop, unsigned long int n)

Compute the nth Fibonacci number and store the result in rop.

Go to the first, previous, next, last section, table of contents.