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.
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.
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
NULLthen that value is not computed.
When b is odd the Jacobi symbol and Kronecker symbol are identical, so
mpz_kronecker_uietc 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
These functions are designed for calculating isolated Fibonacci numbers. When a sequence of values is wanted it's best to start with
mpz_fib2_uiand iterate the defining F[n+1]=F[n]+F[n-1] or similar.
These functions are designed for calculating isolated Lucas numbers. When a sequence of values is wanted it's best to start with
mpz_lucnum2_uiand 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_lucnum2_ui. The formulas for going from Fibonacci to Lucas can be found in Lucas Numbers Algorithm, the reverse is straightforward too.