|
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
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
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 ar2inot = - 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 an - 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.1013 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.1013
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: parameter) : RngIntElt -> BoolElt
Proof: BoolElt Default: true
Returns true iff the integer n is prime. A rigorous
method will be used, unless n > 34 .1013 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).
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!
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.
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.1013, 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.
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.
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).
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: 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.
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 < 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 .1013 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).
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 .1013 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).
PrimeDivisors(n) : RngIntElt -> [RngIntElt]
A sequence containing the distinct prime divisors of the positive integer |n|.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
