Том 3. Простые числа. Долгая дорога к бесконечности | страница 72

— 1)!  —1 (mod р). Однако, как мы упоминали выше, любая формула, содержащая факториал, является недопустимой для компьютерных алгоритмов, потому что быстрый рост функции будет сильно замедлять вычисления.

Существуют также многочлены для «генерации» простых чисел, подобные тем, что использовал Эйлер, чтобы получить список 40 простых чисел с помощью функции f(х) = х^>2 + х + 41, которая генерирует простые числа для каждого значения х.

Например,

х = 0; f(0) = 0 + 0 +41 = 41;

х = 1; f(1) = 1 + 1 + 41 = 43;

х = 2; f(2) = 4 + 2 + 41 = 47.

Однако формула не работает начиная со значений 41 и 42, при подставлении которых получаются составные числа:

х = 41; f(41) = 1681 + 41 + 41 = 1763;

х = 42; f(42) = 1764 + 42 + 42 = 1848.

Эйлер продолжил изучение этого многочлена и пришел к выводу, что многочлен более общего вида, х^>2 — х + q, будет генерировать простые числа для значений х между 0 и q — 2. Существуют также многочлены, открытые Джонсом, Сато, Вада и Вьенсом в 1976 г., которые генерируют только простые числа при подставлении значений их переменных. Эти довольно сложные многочлены содержат 28 переменных. Они не представляют большой практической пользы: если получается положительное значение, оно является простым числом, но в большинстве случаев (почти всегда) результат является отрицательным числом.

В настоящее время большинство известных простых чисел (мы всегда имеем в виду большие простые числа) являются так называемыми простыми числами Мерсенна. Причина этого — в наличии теста простоты Люка-Лемера, который эффективно работает для чисел такого типа. Напомним, что число Мерсенна имеет вид 2^>n  — 1. Когда такое число является простым, оно называется «простым числом Мерсенна». На момент 14 апреля 2011 г. известно только 47 простых чисел Мерсенна. Самым большим из них является число 2^>43112609—1, которое имеет почти 13 млн цифр.