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 = k2n + 1 with an odd k where k < 2n. 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 p − 1 2 ≡ − 1 ( mod p ) {\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}} . In this case, p is called a Proth prime.
Proth's Test Only one such value of a need be found for the test to deterministically confirm primality, provided that p is a Proth number. Verifying that p is a Proth number is a triviality. This is a practical test because, if p is prime, then any chosen a has about a 50 percent chance of working, and if p is not prime, then no chosen a will work. Furthermore, since the calculation is modulo p, only values of a smaller than p have to be considered.
Systematic naïve variant If p is Proth composite, then no base a will work to bear witness of primality. If any one base a bears witness, then primality is confirmed. If none do, then compositeness is confirmed. This is because the inverse of Proth's theorem is also true:
If no a exists such that a p − 1 2 ≡ − 1 ( mod p ) {\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}} , and p is a Proth number, then p is composite. The contrapositive of this statement is that if p is a Proth prime, such an a value is guaranteed to exist. Indeed, if p is a Proth prime then we expect roughly half of all a-values to satisfy the congruence, in the general case. On the other hand, if the second condition is not met - if p is not a Proth number - then compositeness cannot be guaranteed (the inverse is not generally true for non-Proth), even if the first condition of congruence is met. 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.
Probabilistic Monte Carlo Variant As 50% of bases a are expected to bear witness to primality, if p is indeed prime, then we may form a Monte Carlo probabilistic test thus: if the test is repeatedly performed m times, each iteration with a random a, each time failing to confirm primality, then we may infer that p is probably composite - this is in contrast to the probably prime results typical of other Monte Carlo algorithms such as the Miller-Rabin test. An approximate upper bound error probability ε < 2−m of a prime being falsely identified as composite can also be inferred. A composite will, however, never be falsely identified as prime. This probabilistic implementation is not typically performed. Even though it is far more efficient than the deterministic naïve test, with computational efficiency on par with the Miller-Rabin test, it can still be improved both in performance runtime and in accuracy (or definitiveness).
Las Vegas Variant The Las Vegas formulation of Proth's test is by far the most efficient of the variants, and as definitive as the deterministic variant. This is the variant typically employed, though there are some nuances in implementation approach still. In practice, a quadratic nonresidue of p is found and taken as the value of a. Since, if a is a quadratic nonresidue modulo p then the converse of Proth's theorem is also true (if Euler's criterion does not yield –1 then p is composite) and the test becomes conclusive (bidirectional). The theorem may be restated:
For all Proth numbers p, and for any quadratic nonresidue a of p, p is prime if and only if a p − 1 2 ≡ − 1 ( mod p ) {\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}} . A quadratic nonresidue a of p may be identified when the Legendre symbol is –1, thus for such an a-value:
( a p ) = − 1. {\displaystyle \left({\frac {a}{p}}\right)=-1.}
… excerpt ends here. Continue reading the full article.
