Энрике Грасиан - Мир математики. т.3. Простые числа. Долгая дорога к бесконечности

1. Равенство классов Р и NP.

2. Гипотеза Римана.

3. Теория Янга-Миллса.

4. Уравнения Навье-Стокса.

5. Гипотеза Бёрча-Свиннертон-Дайера.

6. Гипотеза Ходжа.

7. Гипотеза Пуанкаре.

Учитывая сложность и важность предложенных задач, финансовые консультанты господина Клэя сомневались в том, что Институту когда-нибудь придется выплачивать эти призы. Тем не менее, в 2006 г. российский математик Григорий Перельман к удивлению всего мира решил седьмую задачу, доказав гипотезу Пуанкаре. Однако по личным причинам он отказался от медали Филдса, присужденной ему на 25-м Международном конгрессе математиков в Мадриде. Он также отказался от награды института Клэя.

* * *

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

Существует много геометрических моделей для поиска простых чисел. Иногда они могут ввести в заблуждение неопытных новичков, так как представлены в виде формул, по которым можно найти все простые числа. Но в действительности эти модели являются не более чем решетом Эратосфена или другим представлением решета с помощью геометрических методов. Хотя некоторые из них действительно гениальны.

Одна из самых интересных моделей была разработана российскими математиками Юрием Матиясевичем(род. в 1947) и Борисом Стечкиным(1920–1995) с использованием параболы (см. ниже). Две ветви параболы разделены горизонтальной осью, на которой отмечена последовательность натуральных чисел. Затем проводятся перпендикуляры к оси в точках, соответствующих квадратам натуральных чисел. Например, в точке +4 проведен перпендикуляр, и точки его пересечения с ветвями параболы обозначены числом 2. Геометрический смысл перпендикуляра состоит в том, что он представляет собой произведение 2 x 2. Аналогично мы проводим другой перпендикуляр в точке 9, представляющий собой произведение 3 x 3, и так далее вдоль оси.

Когда все квадраты чисел на оси будут таким образом представлены точками на параболе, каждая точка на одной ветви параболы соединяется со всеми точками на другой ветви, то есть точка 2 верхней ветви параболы соединяется с точками 2, 3, 4, 5 и так далее на нижней. Каждый из этих отрезков пересечет ось в точке, соответствующей произведению двух соединенных чисел: например, отрезок, соединяющий числа 2 и 3, пересекает ось в точке 6. В конце концов натуральные точки на оси, через которые не проходит ни один из таких отрезков, будут являться простыми числами. Это очень показательный пример геометрического решета.

Алгебраические реализации решета более полезны для разработки быстрых вычислительных алгоритмов. Одной из таких реализаций является решето Аткина, предложенное Артуром Аткиным и Дэниелом Бернштейном. Этот алгоритм позволяет найти все простые числа, меньшие или равные данному натуральному числу.

Геометрическое решето, разработанное Юрием Матиясевичеми Борисом Стечкиным для поиска простых чисел (они отмечены серыми точками на рисунке). Обратите внимание: через них не проходит ни один отрезок.

В некотором смысле это улучшенная версия решета Эратосфена. Когда мы говорим «улучшенная», мы на самом деле имеем в виду «обновленная», так как решето Аткина, строго говоря, уступает решету Эратосфена. Эта версия устраняет числа, кратные не простым числам, а только квадратам простых чисел.

Конечно, в идеале хотелось бы получить формулу, которая связывает каждое натуральное число n с n -м простым числом. Мы видели, что математики пытались найти эту формулу на протяжении по крайней мере 3000 лет. Функции, которые у нас имеются, позволяют вычислять простые числа практическим способом. Например, доказано (теорема Вильсона), что р является простым числом тогда и только тогда, когда ( р — 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 млн цифр.

* * *

ПРОЕКТ GIMPS

Широкомасштабный интернет-проект по поиску простых чисел Мерсенна ( GIMPS— Great Internet Mersenne Prime Search ) начался по инициативе Джорджа Вольтмана и использует сеть соединенных через интернет персональных компьютеров добровольцев (любой желающий может зарегистрироваться). Эти компьютеры работают параллельно и в совокупности представляют собой вычислительные мощности, превосходящие возможности любого суперкомпьютера. Каждый доброволец устанавливает соответствующее программное обеспечение, и его компьютер выполняет вычисления в периоды простоя. Проект был запущен в 1997 г., а к августу 2009 г. было найдено в общей сложности 12 новых простых чисел Мерсенна. Фонд Электронных Рубежей ( EFF— Electronic Frontier Foundation ) предложил приз в 150 тысяч долларов США за нахождение простого числа, состоящего по меньшей мере из 10 миллионов десятичных цифр. 23 августа 2008 г. приз был присужден Эдсону Смиту из Калифорнийского университета за нахождение числа 2 43112609— 1.