[Next][Prev] [Right] [Left] [Up] [Index] [Root]

Primes and Primality Testing

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

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 arnot equiv1 mod n quadand a>not = - 1 mod n for i=0, 1, ..., k - 1 where r odd, and k are such that n - 1=r.2k. A witness never falsely claims that n is composite, because for prime n it must hold that a1 = 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 4k.

A slight adaptation of this compositeness test can be used for primality proofs in a bounded range. There are no composites smaller than 34.103 for which a witness does not exist among a=2, 3, 5, 7, 11, 13, 17 ([Jae93]). Using these values of a for candidate witnesses it is certain that for any number n less than 34.103 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 François 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 ([AM93]).

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
Returns true iff the integer n is prime. A rigorous method will be used, unless n > 34 .103 and the optional parameter Proof is set to Proof := false, in which case the result indicates that n is a probable prime (a strong pseudoprime to 20 bases).
SetVerbose("ECPP", v) : MonStgElt, Elt ->
Sets the verbose level for output when the ECPP algorithm is used in the above primality tests. The legal values are true, false, 0, 1 and 2 (false and true are the same as 0 and 1 respectively). Level 1 outputs only basic information about the times for the top-level stages (downrun and uprun). Level 2 outputs full information about every step : this level is very verbose!
PrimalityCertificate(n) : RngIntElt -> List
IsPrimeCertificate(cert) : List -> BoolElt
    ShowCertificate: BoolElt            Default: true
    Trust: RngIntElt                    Default: 0
PrimalityCertificate is a variant on IsPrime which uses ECPP and outputs a certificate of primality at the conclusion. If the number n is actually proven to be composite or the test fails, then a runtime error occurs. The certificate is a Magma list with data in the format described in [AM93].

To verify that a given number is prime from its primality certificate, the function IsPrimeCertificate is used. By default, this outputs only the result of the verification : true or false. If the user wishes to see the stages of the verification, the parameter ShowCertificate should be set to true. This is rather verbose as it shows the verification of primality of all small factors that need to be shown to be prime at each substage of the algorithm. It is usually more convenient to set the parameter Trust to a positive integer N which means that asserted primes less than N are not checked. This slightly reduces the time for the verification, but more importantly, it greatly reduces the output of ShowCertificate.

IsProbablePrime(n: parameter) : RngIntElt -> BoolElt
IsProbablyPrime(n: parameter) : RngIntElt -> BoolElt
    Bases: RngIntElt                    Default: 20
Returns true if and only if the integer n is a probable prime. More precisely, the function returns true if and only if either n is prime for n < 34.103, or n is a strong pseudoprime for 20 random bases b with 1 < b < n. By setting the optional parameter Bases to some value B, the number of random bases used is B instead of 20.
IsPrimePower(n) : RngIntElt -> BoolElt, RngIntElt, RngIntElt
Returns true if and only if the integer n is a prime power; that is, if n equals pk for some prime p and exponent k≥1. If this is the case, the prime p and the exponent k are also returned, Note that the primality of p is rigorously proven.

Example RngInt_RepUnits (H18E6)

This piece of code uses 5 Miller-Rabin tests to find the next probable repunit-prime (consisting of all 1's as decimal digits), using the fact that primes of this form consist of a prime number of digits:

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

> NextPPRepunit(1);
2
> NextPPRepunit(2);
19
> NextPPRepunit(19);
23
> NextPPRepunit(23);
317
So we found a 317 digit prime (although we should check genuine primality, using IsPrime)! We leave it to the reader to find the next (it has more than 1000 decimal digits).

Other Functions Relating to Primes

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) : RngIntElt -> RngIntElt
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.
PrimesUpTo(B) : RngIntElt -> [RngIntElt]
This function lists the primes up to (and including) the (positive) bound B. The algorithm is not super-optimised, but is reasonable.
PrimesInInterval(t, b) : RngIntElt, RngIntElt -> [RngIntElt]
This function lists the primes in the interval from b to e, including the endpoints. The algorithm is not very optimised.
NthPrime(n) : RngIntElt -> RngIntElt
Given a number n, this function returns the nth prime.
RandomPrime(n: parameter) : RngIntElt -> RngIntElt
    Proof: BoolElt                      Default: true
A random prime integer m such that 0 < m < 2n, where n is a small non-negative integer. The function always returns 0 for n=0 or n=1. A rigorous method will be used to check primality, unless m > 34 .103 and the optional parameter `Proof' is set to Proof := false, in which case the result indicates that m is a probable prime (of order 20).
RandomPrime(n, a, b, x: parameter) :RngIntElt, RngIntElt, RngIntElt -> BoolElt, RngIntElt
    Proof: BoolElt                      Default: true
Tries up to x iterations to find a random prime integer m congruent to a modulo b such that 0 < m < 2n. Returns true, m if found, or false if not found. n must be larger than 0. a must be between 0 and b - 1 and b must be larger than 0. A rigorous method will be used to check primality, unless m > 34 .103 and the optional parameter `Proof' is set to Proof := false, in which case the result indicates that m is a probable prime (of order 20).
PrimeBasis(n) : RngIntElt -> [RngIntElt]
PrimeDivisors(n) : RngIntElt -> [RngIntElt]
A sequence containing the distinct prime divisors of the positive integer |n|.
 [Next][Prev] [Right] [Left] [Up] [Index] [Root]

Version: V2.14 of Fri May 2 07:34:13 EST 2008