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.

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^{>}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^{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. There are no composites smaller than
34.10^{3} 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.10^{3}
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`.

Proof: BoolElt Default:true

Returnstrueiff the integer n is prime. A rigorous method will be used, unless n > 34 .10^{3}and the optional parameterProofis set toProof := false, in which case the result indicates that n is a probable prime (a strong pseudoprime to 20 bases).

Sets the verbose level for output when the ECPP algorithm is used in the above primality tests. The legal values aretrue,false, 0, 1 and 2 (falseandtrueare 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!

ShowCertificate: BoolElt Default:true

Trust: RngIntElt Default: 0

PrimalityCertificateis a variant onIsPrimewhich 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 aMagmalist with data in the format described in [AM93].To verify that a given number is prime from its primality certificate, the function

IsPrimeCertificateis used. By default, this outputs only the result of the verification :trueorfalse. If the user wishes to see the stages of the verification, the parameterShowCertificateshould be set totrue. 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 parameterTrustto 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 ofShowCertificate.

Bases: RngIntElt Default: 20

Returnstrueif and only if the integer n is a probable prime. More precisely, the function returnstrueif and only if either n is prime for n < 34.10^{3}, or n is a strong pseudoprime for 20 random bases b with 1 < b < n. By setting the optional parameterBasesto some value B, the number of random bases used is B instead of 20.

Returnstrueif and only if the integer n is a prime power; that is, if n equals p^{k}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.

> 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); 317So we found a 317 digit prime (although we should check genuine primality, using

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.

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 := trueby default) can be set toProof := false, to indicate that the next probable prime (of order 20) may be returned.

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 := trueby default) can be set toProof := false, to indicate that the previous probable prime (of order 20) may be returned.

This function lists the primes up to (and including) the (positive) bound B. The algorithm is not super-optimised, but is reasonable.

This function lists the primes in the interval from b to e, including the endpoints. The algorithm is not very optimised.

Given a number n, this function returns the nth prime.

Proof: BoolElt Default:true

A random prime integer m such that 0 < m < 2^{n}, 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 .10^{3}and the optional parameter `Proof' is set toProof := false, in which case the result indicates that m is a probable prime (of order 20).

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 < 2^{n}. 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 .10^{3}and the optional parameter `Proof' is set toProof := false, in which case the result indicates that m is a probable prime (of order 20).

A sequence containing the distinct prime divisors of the positive integer |n|.[Next][Prev] [Right] [Left] [Up] [Index] [Root]

Version: V2.14 of