Proth prime

A Proth prime is a Proth number that is also a prime number. Given a Proth number $p$, if one can find a coprime integer $b$ such that

$$b^{\frac{p-1}{2}}\equiv -1modp$$

then $p$ is a prime, and specifically a Proth prime (this is a theorem first stated by François Proth). Thanks to this theorem, Yves Gallot created an algorithm used in a primality-testing program employed by the Seventeen or Bust project. The first few Proth primes are 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, etc. (listed in A080076 of Sloane’s OEIS). Konstantin Agafonov’s discovery of the Proth prime $19249\times 2^{13018586}+1\approx 1.484360328715661\times {10}^{3918989}$ currently makes for the largest known prime that is not a Mersenne prime.

Title	Proth prime
Canonical name	ProthPrime
Date of creation	2013-03-22 17:21:11
Last modified on	2013-03-22 17:21:11
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	7
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 11A51