François Proth trabaja sobre varias pruebas para identificar números primos, en 1.878 propone la siguiente:
N = k × 2 n + 1 siendo 2 n > k y k impar, si existe un natural a para a (N-1)/2 ? -1 (mod N) entonces N es primo.
Es una prueba determinista pero, tiene un inconveniente, su tiempo de respuesta es muy aleatorio
Los números de Proth tienen la siguiente forma: N = k × 2 n + 1 siendo 2 n > k y k impar. Los primeros números son:
3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, …
Sus primeros primos: 3, 5, 13, 17, 41, 97, 113, 193, 241,257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, … y los mayores conocidos:
| Fecha | Primo | Dígitos |
| 2.016 | 10223×231172165 + 1 | 9.383.761 |
| 2.017 | 168451×219375200 + 1 | 5.832.522 |
| 2.007 | 19249×213018586 + 1 | 3.918.990 |
| 2.014 | 3×210829346 + 1 | 3.259.959 |
| 2.005 | 27653×29167433 + 1 | 2.759.677 |
| 2.010 | 90527×29162167 + 1 | 2.758.093 |
| 2.004 | 28433×27830457 + 1 | 2.357.207 |
| 2.015 | 161041×27107964 + 1 | 2.139.716 |
| 2.011 | 3×27033641 + 1 | 2.117.338 |
| 2.007 | 33661×27031232 + 1 | 2.116.617 |