Primality testing algorithms enable the user to certify the primality of prime integers. Proving the primality of very big integers can be time consuming and therefore in some of the algorithms using primes and factorization of integers the user can speed up the algorithm by explicitly allowing Magma to use probable primes rather than certified primes.

A probable prime is an integer that has failed some compositeness test; if an integer passes a compositeness test it will be composite, but there is a (small) probability that a composite number will fail the test and is hence called a probable prime. Each Miller-Rabin test for instance, has a probability of less than 1/4 of declaring a composite number probably prime; in practice that means that numbers that fail several such cheap independent Miller-Rabin compositeness tests will be prime.

Unless specifically asked otherwise, Magma will use rigorous primality proofs.

Subsections

• Primality
• Other Functions Relating to Primes

If a positive integer n is composite, this can be shown quickly by exhibiting a witness to this fact. A witness for the compositeness of n is an integer 1<a<n with the property that a^r not equiv1 mod n quadand a^(r2^i)not = - 1 mod n for i=0, 1, ..., k - 1 where r odd, and k are such that n - 1=r.2^k. A witness never falsely claims that n is composite, because for prime n it must hold that a^(n - 1) = 1 mod n and only +-1 are square roots of 1 modulo prime n. Moreover, it has been shown that a fraction of at least 3/4 of all a in the range 2 ... n - 1 will witness the compositeness of n. Thus randomly choosing a will usually quickly expose compositeness. Unless more than 3/4 of all possibilities for a are checked though (which in practice will be impossible for reasonable n) the procedure of checking k bases a at random for being a witness (often referred to as `Miller-Rabin') will not suffice to prove the primality of n; it does however lend credibility to the claim that n is most likely prime if among k (say 20) random choices for a no witness for compositeness has been found. In such cases n is called probably prime of order k, and in some sense the probability that n is composite is less than 4^(-k).

A slight adaptation of this compositeness test can be used for primality proofs in a bounded range. Thus the finite number of composites smaller than 25.10^9 have been identified for which a witness does not exist among a=2, 3, 5, 7. Using these values of a for candidate witnesses first it is certain that for any number n less than 25.10^9 not appearing in the list of exceptions, the test will either find a witness or correctly declare n prime.

But even for large integers it is thus usually easy to identify composites without finding a factor; to be certain that a large probable prime is truly prime, a primality proving algorithm is invoked. Magma uses the ECPP (Elliptic Curve Primality Proving) method, as implemented by Francois Morain (Ecole Polytechnique and INRIA). The ECPP program in turn uses the BigNum package developed jointly by INRIA and Digital PRL. This ECPP method is both fast and rigorous, but for large integers (of say more than 100 decimal digits) it will be still be much slower than the Miller-Rabin compositeness test. The method is too involved to be explained here; we refer the reader to the literature. [A.O.L. Atkin, F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29--68]

The IsPrime function invokes ECPP, unless a Boolean flag is used to indicate that only `probable primality' is required. The latter is equivalent to a call to IsProbablePrime.

IsPrime(n) : RngIntElt -> BoolElt

IsPrime(n: parameter) : RngIntElt -> BoolElt

    Proof: BoolElt                      Default: true

True iff the integer n is prime. A rigorous method will be used, unless n > 25 .10^9 and the optional parameter `Proof' is set to Proof := false, in which case the result indicates that n is a probable prime (of order 20).

IsProbablePrime(n: parameter) : RngIntElt -> BoolElt

    Bases: RngIntElt                    Default: 20

True iff the integer n is a probable prime. This means that the function returns true iff n is prime for n < 25.10^9; otherwise the function returns true iff n is a strong pseudoprime for 20 random bases b with 1 < b < n. By setting the optional parameter Bases to B the number of bases tried at random is changed to B instead of 20.

True iff the integer n is a prime power; that is, if n equals p^k for some prime p and exponent k >= 1. If so, the prime p and the exponent k are also returned (the primality of p is rigorously proven).

> NextPPRepunit := function(nn)
>    n := nn;
>    repeat
>       n := NextPrime(n);
>    until IsProbablePrime( (10^n-1) div 9 : Bases := 5);
>    return n;
> end function;

> NextPPRepunit(1);
2
> NextPPRepunit(2);
19
> NextPPRepunit(19);
23
> NextPPRepunit(23);
317

The functions NextPrime and PreviousPrime can be used to find primes in the neighbourhood of a given integer. After sieving out only multiples of very small primes, the remaining integers are tested for primality in order. Again, a rigorous method is used unless the user flags that probable primes suffice.

The PrimeDivisors function is different from all other functions in this section since it requires the factorization of its argument.

NextPrime(n) : RngIntElt -> RngIntElt

NextPrime(n: parameter) : RngIntElt -> RngIntElt

    Proof: BoolElt                      Default: true

The least prime number greater than n, where n is a non-negative integer. The primality is proved. The optional boolean parameter `Proof' (Proof := true by default) can be set to Proof := false, to indicate that the next probable prime (of order 20) may be returned.

PreviousPrime(n: parameter) : RngIntElt -> RngIntElt

    Proof: BoolElt                      Default: true

The greatest prime number less than n, where n >= 3 is an integer. The primality is proved. The optional boolean parameter `Proof' (Proof := true by default) can be set to Proof := false, to indicate that the previous probable prime (of order 20) may be returned.

PrimeDivisors(n) : RngIntElt -> [RngIntElt]

A sequence containing the distinct prime divisors of the positive integer |n|.