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 ar ≢ 1 mod n and ar2i ≢ - 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.
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!
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.
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.
> 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 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.
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.
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. The limit on B is 230 - 1 for practical reasons, as otherwise the memory requirements can become too large with non-small integers (see below).
This function lists the primes in the interval from b to e, including the endpoints. The algorithm is not very optimised. The interval must be smaller than 230 in size, but if there are non-small integers (>230) involved then these will create a large memory overhead in any case. For instance, the PrimesUpTo intrinsic for 230 - 1 returns 54400028 primes in 650 megabytes, while the PrimesInInterval intrinsic for (230 + 1, 231 - 1) takes over 5 gigabytes for its array of 50697537 primes.
Given a number n, this function returns the nth prime. This is implemented for primes up to 1010, or n≤455052511.
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).
A sequence containing the distinct prime divisors of the positive integer |n|.