The 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 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.
Proof: BoolElt Default: true
The least prime number greater than n, where n is a non-negative integer. The optional boolean parameter `Proof' (Proof := true by default) can be set to Proof := false, to indicate that the next probable prime may be returned.
Proof: BoolElt Default: true
The greatest prime number less than n, where n >= 3 is an integer. The optional boolean parameter `Proof' (Proof := true by default) can be set to Proof := false, to indicate that the previous probable prime may be returned.
Proof: BoolElt Default: true
True if the positive integer n is a 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).
Al: MonStgElt Default: "Division"
Test the positive integer n for primality using the algorithm specified by the parameter Al, (default division) using the optional parameters that depend on the algorithm as described below. The value returned by this function is -1 (if n is composite), +1 (if n is prime), or 0 (if the Selfridge or the Pocklington algorithm fails).
Lower: RngIntElt Default: 2
Upper: RngIntElt Default: sqrt{n}
Use trial division to prove whether or not n is prime. If the optional parameters Lower := a and Upper := b are set to positive integers a <= b, this function returns -1 if n has a divisor r with a <= r <= b and +1 otherwise. (By default a = 2 and b = sqrt n.)
Factorization: [RngIntElt] Default: [ ]
The Selfridge primality test is employed, which requires the factorization of n - 1. The user can supply the factorization of n - 1 by setting the optional parameter Factorization := [ <p_1, k_1>, ..., <p_r, k_r> ], where n = p_1^(k_1)p_2(k_2) ... p_r^(k_r) and the p_i are distinct primes.
Factorization: [RngIntElt] Default: [ ]
Bound: RngIntElt Default: 1
The Pocklington primality test is employed. Again, the test requires the factorization of n - 1; the user may supply a partial factorization of n - 1 via the optional parameter Factorization. To complete the test, the factorization of n - 1 does not have to be complete, but the factored part must be greater than the unfactored part divided by some bound, below which it is known that no prime factors exist. This bound is one by default, but may be set to larger values by the user, using the parameter Bound.
Bases: RngIntElt Default: 25
The Miller-Rabin probabilistic primality test is employed. In this case Primality returns -1 if n is definitely composite and +1 is n is probably prime. The number of bases employed by the Miller-Rabin test may be specified using the optional parameter Bases which has the default value 25.
> NextRepunit := function(nn) > n := nn; > repeat > n := NextPrime(n); > until Primality( (10^n-1) div 9 : Al := "MillerRabin", Bases := 5) eq 1; > return n; > end function;The first few cases are easy:
> print NextRepunit(1); 2 > print NextRepunit(2); 19 > print NextRepunit(19); 23 > print NextRepunit(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).
Bound: RngIntElt Default: 1000
Given a positive integer n, this function returns a sequence of triples which constitutes a proof that n is prime. The optional parameter Bound may be used to specify an upper bound on primes for which no proof is required (default Bound := 1000).The form of the certificate is a sequence of triples of three integers. Each triple of three integers consists of a prime p, a divisor q of p - 1, and an integer a of multiplicative order modulo p divisible by q^k, where q^k is the largest power of q dividing p - 1. One of the divisors q of p may be composite, and this is indicated by the base a being negative. For each of the prime divisors q smaller than or equal to Bound no proof of primality is produced, but an entry of the form (q, 0, 0) is inserted.
> n := NextPrime(10^25); > print PrimeCertificate(n);This produces the following certificate as output:
[ < 10000000000000000000000013, 9881422924901185770751, 2 >, < 10000000000000000000000013, 23, 2 >, < 10000000000000000000000013, 11, 2 >, < 10000000000000000000000013, 2, 2 >, < 9881422924901185770751, 2, 3 >, < 9881422924901185770751, 4093, 2 >, < 9881422924901185770751, 11, 2 >, < 9881422924901185770751, 5, 2 >, < 9881422924901185770751, 3, 2 >, < 9881422924901185770751, 97544444443469, -2 >, < 4093, 31, 2 >, < 4093, 11, 2 >, < 4093, 3, 2 >, < 4093, 2, 2 >, < 31, 0, 0 >, < 23, 0, 0 >, < 11, 0, 0 >, < 5, 0, 0 >, < 3, 0, 0 >, < 2, 0, 0 > ]Each of the first four triples is of the form <n, p, 2>, with p a prime divisor of n - 1; let p^k be the largest power of p dividing n - 1. The triple <n, p, 2> indicates that 2^((n - 1)/p) - 1 is coprime to n, while 2^(n - 1) = 1 mod n. This is easily verified:
> s := PrimeBasis( n-1 ); > p := s[4]; > print Gcd( n-1, Modexp( 2, (n-1) div p, n) ); 1 > print Modexp(2, n-1, n); 1
Thus such a triple proves that every prime divisor must be congruent to 1 modulo p^k and the four triples together then prove that n is prime, provided we prove recursively that each p is prime.
The next six lines of the certificate do so for p = 9881422924901185770751. Again, for each triple <p, q, r> it is true that r^((p - 1)/q) - 1 is coprime to p, while r^(p - 1) = 1 mod p. In this case, however, p - 1 is not completely factored: the minus sign in the certificate indicates that 97544444443469 is a composite factor. This factor even exceeds sqrt(p - 1), but still the above provides enough information to show that 9881422924901185770751 is prime using Pocklington's theorem, since it has been checked that 9881422924901185770750 has no prime factors less than 1000 other than those listed (2, 3, 5, 11) and because 2.3^2.5^3.11.4093.1000 exceeds sqrt(p - 1).
Finally, the certificate for 4093 is listed, but not those for the `visibly' prime numbers less than 1000.