The Lucas-Lehmer Prime Number Test
Французский математик Эдуард Лукас в XIX веке разработал метод проверки простоты чисел, который используется и спустя 150 лет. Он доказал, что 39-значное число 2¹²⁷ - 1 является простым, применив созданный им тест, который до сих пор остается эффективным для чисел специального вида - простых Мерсенна (чисел вида 2^p - 1, где p - простое). Крупнейшее известное простое число на октябрь 2025 года имеет более 41 миллиона цифр и также является числом Мерсенна.
Тест Лукаса-Лемера работает следующим образом: создается последовательность, где s₀ = 4, а каждый следующий член вычисляется как sₙ = sₙ₋₁² - 2. Число 2^p - 1 будет простым тогда и только тогда, когда (p-2)-й член этой последовательности делится на 2^p - 1 без остатка. Этот метод позволил Лукасу доказать простоту огромного числа без помощи компьютера, что остается рекордом и по сей день.