GIMPS

---

GIMPS (Great Internet Mersenne Prime Search) — широкомасштабный проект добровольных вычислений по поиску простых чисел Мерсенна.

Определение того, является ли данное число простым, в общем случае не такая уж простая задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, предложенный (и строго обоснованный теоретически) детерминированный алгоритм практически непригоден, в виду его большой, хотя и полиномиальной, сложности. Поэтому в криптографии с открытым ключом, где используются простые числа порядка ${\displaystyle 10^{300}}$, простоту по-прежнему определяют с помощью эффективных вероятностных тестов, таких как тест Миллера — Рабина. Если практика довольствуется числами, являющимися простыми с вероятностью близкой к ${\displaystyle 1}$, то теория такие числа не приемлет: если про число утверждается, что оно простое, это должно быть строго доказано. Эта разница подчёркивается в разделении алгоритмов на вероятностные и детерминированные.

Если задаться вопросом, какое же наибольшее простое число^[1] известно человечеству — то ответом будет какое-то простое число Мерсенна. Числа Мерсенна имеют вид ${\displaystyle M_{p}=2^{p}-1}$. Заметим, что простота числа ${\displaystyle 2^{p}-1}$ влечёт простоту ${\displaystyle p}$; в противном случае ${\displaystyle p=xy}$ для ${\displaystyle x,y>1}$ и число ${\displaystyle 2^{p}-1=2^{xy}-1}$ не будет простым в виду делимости на ${\displaystyle 2^{x}-1}$ (как, впрочем, и на ${\displaystyle 2^{y}-1}$).

---