Proth's theorem
In number theory, Proth's theorem is a theorem which forms the basis of a primality test for Proth numbers known as Proth's test.
≈ 9 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In number theory, Proth's theorem is a theorem which forms the basis of a primality test for Proth numbers known as Proth's test. Proth numbers, sometimes called Proth Numbers of the First Kind, are those integers p which take the form p = k2 n + 1 with an odd k where k n . For Proth Numbers of the Second Kind, see related topic Riesel numbers.
The theorem is also named after the French mathematician and original publisher of the theorem, François Proth. The theorem states that for any Proth number (of the first kind), p, p is prime if there exists an integer a for which Euler's criterion yields –1, that is, : a^{\frac{p-1}{2}}\equiv -1 \pmod{p} . In this case, p is called a Proth prime.
In number theory, Proth's theorem is a theorem which forms the basis of a primality test for Proth numbers known as Proth's test. Proth numbers, sometimes called Proth Numbers of the First Kind, are those integers p which take the form p = k2 n + 1 with an odd k where k n . For Proth Numbers of the Second Kind, see related topic Riesel numbers.
The theorem is also named after the French mathematician and original publisher of the theorem, François Proth. The theorem states that for any Proth number (of the first kind), p, p is prime if there exists an integer a for which Euler's criterion yields –1, that is, a^{\frac{p-1}{2}}\equiv -1 \pmod{p} . In this case, p is called a Proth prime.
As such, we may systematically check all base values [2, p − 1] to verify compositeness (note that a = 0 and a = 1 will never work), unless and until one is found to confirm primality. This process, as it is stated, though the most straightforward and trivial, can be made more efficient.
In principle, since if p is prime, there is roughly a 50% chance of a chosen a of proving primality, we may make the process slightly more efficient by checking about one-half of all possible a-values smaller than p - we expect half of said values to satisfy the congruence. Once more than p/2 distinct values of a have been tested, compositeness is deterministic.
This is because, if p is prime then we expect half of all bases to bears witness; by the pigeonhole principle, once more than half have been checked, we can deduce that none will bear witness, and if no base value a will work, then p is composite. If on the other hand p is prime, then at least one of the values checked would inevitably have borne witness, as would all remaining unchecked values.
This variation of the test is similar to the deterministic variant of the Fermat primality test. Both of these naïve variants are grossly inefficient and never employed in practice. Note that both of these approaches represent significantly more computational work than simple brute force trial division (Schoolhouse method) in the worst case scenario. \left(\frac{a}{p}\right)=-1 .
For such a value of a, the test is deterministic for both primality and compositeness; thus, for such an a the check against Proth's/Euler's criteria only requires only one iteration: congruence or non-congruence to -1 is wholly descriptive of primeness. The difficulty is in finding such of an a-value.
Given a Proth number p = k2 n + 1, particular forms of p, k, and n have been identified that correspond to predetermined quadratic nonresidue values that are appropriate for use. It has been shown that: If p > 3 and 3 \nmid k , then a=3 is always a quadratic nonresidue (candidate) and therefore a valid base to check, and so: 3^{\frac{p-1}{2}} \equiv -1 \pmod{p} if and only if p is prime.
This is the basis of Pépin's test for Fermat numbers and their corresponding primes, wherein k = 1 is indivisible by 3. If p > 8 and p is 3 or 5 modulo 8, then a=2 is always a quadratic nonresidue (candidate) and therefore a valid base to check, and so: 2^{\frac{p-1}{2}} \equiv -1 \pmod{p} if and only if p is prime.
If p > 5 and p is 2 or 3 modulo 5, then a = 5 is always a quadratic nonresidue (candidate) and therefore a valid base to check, and so: 5^{\frac{p-1}{2}} \equiv -1 \pmod{p} if and only if p is prime. Though no such simple rule exists for the case where p is 1 or 4 modulo 5, in the latter 4 mod 5 case, one can increase the chances of finding a quadratic nonresidue candidate systematically by checking values in the narrow vicinities of the two distinct square roots of 5 modulo p. If there are not precisely two distinct square roots (see the Tonelli-Shanks algorithm) then p is not prime.
Direct computation of the nonresidue is still likely more efficient.
Numerical examples
Examples of the theorem include: for p = 3 = 1(2 1 ) + 1, we have that 2 (3−1)/2 + 1 = 3 is divisible by 3, so 3 is prime. for p = 5 = 1(2 2 ) + 1, we have that 3 (5−1)/2 + 1 = 10 is divisible by 5, so 5 is prime. for p = 13 = 3(2 2 ) + 1, we have that 5 (13−1)/2 + 1 = 15626 is divisible by 13, so 13 is prime. for p = 9, which is not prime, there is no a such that a (9−1)/2 + 1 is divisible by 9. The fact that p = 9 is not prime can be deterministically verified by checking that no such a (in mod 9) exists.
This may be done by systematically checking each value of a from 2 to 8 (a = 0 and a = 1 will never work for any p). It is, however, sufficient to check values 2 to 5, or one-half of all possible values under 9. If 9 were a prime then by the pigeonhole principle, at lease one of these values of a will confirm primality, since it is expected that half of them would.
Alternatively, if we employ the deterministic variant wherein the quadratic nonresidue is directly computed, the work requires fewer iterations to confirm both compositeness and primality: for p = 97 = 3(2 5 ) + 1, we have a quadratic nonresidue of a = 5, and 5 (97−1)/2 + 1 = 3552713678800500929355621337890626 is divisible by 97, so 97 is prime. for p = 1537 = 3(2 9 ) + 1, we have a quadratic nonresidue of a = 5, and 5 (1537−1)/2 + 1 = 1052 (mod 1537) is not divisible by 1537, so 1537=29×53 is not prime. In each of the previous two examples, an appropriate value of a was directly computed using a quadratic nonresidue computation such that the results of the test would be conclusive – a valid quadratic nonresidue in both the prime and composite cases.
It was not necessarily to systematically search for an a to witness the prime case, or to reiterate the test a sufficient number of times for the composite. If a quadratic nonresidue cannot be found, or if one does not exist, then we may take this as confirmation of compositeness. b = −1, in which case Proth's criterion is met and p is confirmed to be a Proth prime, as per Proth's theorem, if indeed p is a Proth number.
If p is not a Proth number yet b = −1, then this is indicative, but not conclusive, of primality. Refer to the probabilistic Solovay–Strassen primality test and the Miller-Rabin test. Inconclusive result: b = 1, in which case the test is inconclusive and must be tried again with a new a value.
This condition is what requires reiteration and makes the test probabilistic, as if p were prime, then b = ±1 occurs with roughly equal probability, though the b = 1 condition may still be met with p either composite or non-Proth. This is true unless a happens to also be a quadratic nonresidue of a Proth number p, in which case compositeness is indicated.
Compositeness of p, as per Euler's criterion and the Legendre symbol, which offer early exit conditions when b ≠ ±1. In each of these cases p is not prime and also need not be a Proth number: b 2 = 1, with nontrivial divisors of p being GCD(b ± 1, p). b 2 ≠ 1, where p is proven composite by Fermat's test, base a. b = 0, where p has a nontrivial divisor GCD(a, p).
Proof
The proof for this theorem uses the Pocklington-Lehmer primality test. It is a relatively simple special case to prove Proth's theorem from it. It also closely resembles the proof of Pépin's test.
The proof can be found on page 52 of. When k = n, the Proth number takes the form of p = n2 n + 1. If we relax the condition requiring that k (or n) is odd, these are known as Cullen numbers, with corresponding Cullen primes.
Though Proth's test works when n is odd, Cullen numbers have their own primality tests for arbitrary n. Furthermore, Cullen's primality tests may be generalized to numbers of the form p = nc n + 1, for arbitrary bases c.
History
François Proth (1852–1879) published the theorem in 18781.
See also
Pépin's test (the special case k = 1, where one chooses a = 3) Sierpiński number
External links
de:Prothsche Primzahl nl:Prothgetal
Text derived from https://en.wikipedia.org/w/index.php?oldid=1370713567 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Proth's theorem” publication date (×1) · confidence 0.95 revision URL