Next: Integer Comparisons, Previous: Integer Roots, Up: Integer Functions [Index]
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.
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.
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.
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.
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 is NULL
then that value is not computed.
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.
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). 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.
Calculate the Jacobi symbol (a/b). This is defined only for b odd.
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.
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
.
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.
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).
Set rop to the primorial of n, i.e. the product of all positive prime numbers <=n.
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.
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.
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]