Мир математики. т.3. Простые числа. Долгая дорога к бесконечности
Шрифт:
Когда все квадраты чисел на оси будут таким образом представлены точками на параболе, каждая точка на одной ветви параболы соединяется со всеми точками на другой ветви, то есть точка 2 верхней ветви параболы соединяется с точками 2, 3, 4, 5 и так далее на нижней. Каждый из этих отрезков пересечет ось в точке, соответствующей произведению двух соединенных чисел: например, отрезок, соединяющий числа 2 и 3, пересекает ось в точке 6. В конце концов натуральные точки на оси, через которые не проходит ни один из таких отрезков, будут являться простыми числами. Это очень показательный пример геометрического решета.
Алгебраические реализации решета более полезны для разработки быстрых вычислительных алгоритмов. Одной из таких реализаций является решето Аткина, предложенное Артуром Аткиным и Дэниелом Бернштейном. Этот алгоритм позволяет
Геометрическое решето, разработанное Юрием Матиясевичем и Борисом Стечкиным для поиска простых чисел (они отмечены серыми точками на рисунке). Обратите внимание: через них не проходит ни один отрезок.
В некотором смысле это улучшенная версия решета Эратосфена. Когда мы говорим «улучшенная», мы на самом деле имеем в виду «обновленная», так как решето Аткина, строго говоря, уступает решету Эратосфена. Эта версия устраняет числа, кратные не простым числам, а только квадратам простых чисел.
Конечно, в идеале хотелось бы получить формулу, которая связывает каждое натуральное число n с n– м простым числом. Мы видели, что математики пытались найти эту формулу на протяжении по крайней мере 3000 лет. Функции, которые у нас имеются, позволяют вычислять простые числа практическим способом. Например, доказано (теорема Вильсона), что р является простым числом тогда и только тогда, когда (р — 1)!
Существуют также многочлены для «генерации» простых чисел, подобные тем, что использовал Эйлер, чтобы получить список 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 переменных. Они не представляют большой практической пользы: если получается положительное значение, оно является простым числом, но в большинстве случаев (почти всегда) результат является отрицательным числом.
В настоящее время большинство известных простых чисел (мы всегда имеем в виду большие простые числа) являются так называемыми простыми числами Мерсенна. Причина этого — в наличии теста простоты Люка-Лемера, который
* * *
ПРОЕКТ GIMPS
Широкомасштабный интернет-проект по поиску простых чисел Мерсенна (GIMPS — Great Internet Mersenne Prime Search) начался по инициативе Джорджа Вольтмана и использует сеть соединенных через интернет персональных компьютеров добровольцев (любой желающий может зарегистрироваться). Эти компьютеры работают параллельно и в совокупности представляют собой вычислительные мощности, превосходящие возможности любого суперкомпьютера. Каждый доброволец устанавливает соответствующее программное обеспечение, и его компьютер выполняет вычисления в периоды простоя. Проект был запущен в 1997 г., а к августу 2009 г. было найдено в общей сложности 12 новых простых чисел Мерсенна. Фонд Электронных Рубежей (EFF — Electronic Frontier Foundation) предложил приз в 150 тысяч долларов США за нахождение простого числа, состоящего по меньшей мере из 10 миллионов десятичных цифр. 23 августа 2008 г. приз был присужден Эдсону Смиту из Калифорнийского университета за нахождение числа 243112609 — 1.
Логотип Фонда Электронных Рубежей.
* * *
Единственный способ узнать наверняка — это разделить данное число на все предшествующие ему числа. Если оно не делится ни на одно из них, то оно является простым. Как мы видели в предыдущей главе, извлечение квадратного корня из числа может значительно сократить количество работы. Это хороший метод для небольших чисел и вычислений вручную. Например, мы хотим узнать, является ли число 101 простым или составным. Знание правил делимости может помочь нам избежать ненужной работы. Очевидно, что 101 не делится на 2, так как в противном случае его последняя цифра была бы четной или нулем. Не делится оно и на 3, так как сумма его цифр не делится на 3 (1 + 0 + 1 = 2). Также 101 не делится на 5, иначе оно оканчивалось бы на 0 или на 5. Мы также можем отбросить 4, 6 и 9, так как они кратны 2 или 3. Если мы попытаемся разделить 101 на 7, мы получим 14 и остаток 3. Значит, оно не делится и на 7. Следующее число, которое стоит проверить, — 11 (101, очевидно, не делится на 10). Деление на 11 дает 9 и остаток 2. Здесь мы можем остановиться и сказать, что 101 является простым числом, так как квадратный корень из 101 составляет примерно 10. Это означает, что наше число уже не будет делиться на любые другие оставшиеся числа, меньшие 101.
Этот метод называется перебором делителей и является самым простым и самым надежным. Проблема заключается в том, что он не оправдывает себя в случае очень больших чисел, даже если используется компьютер. Заметим, что для числа из 50 цифр потребуется проверка всех чисел длиной до 25 цифр, что более или менее соответствует корню из данного числа. Компьютеру, который способен выполнять миллиард операций деления в секунду, потребуется более 300 млн лет, чтобы закончить проверку, а к тому времени, вполне вероятно, человечество исчезнет с лица Земли!
Во всяком случае, этот метод работает достаточно хорошо для составного числа, если один из его делителей не является слишком большим. Следует иметь в виду, что для любого числа n вероятность того, что число 2 является одним из его делителей, составляет 50 %, а вероятность того, что делителем является число 3, составляет 33 % и так далее.
С другой стороны, скорость и объем памяти современных компьютеров значительно выросли, так что поиск простого числа в длинном списке иногда более эффективен, чем сложный процесс определения, является ли данное число простым.