РЕШЕТО ЭРАТОСФЕНА

Простые числа. Они так изящны и элегантны. Числа, которые не желают ни в чем принимать участия, которые не размениваются и не делятся, числа, которые остаются сами собой навеки.

Пол Остер

Простые числа – это самые загадочные из всех чисел, открытых математиками. Они делятся только на самих себя и 1, представляют собой некие элементарные частицы мира чисел. Первые несколько из них выделить несложно – 2, 3, 5, 7, 11,13, 17… Более 2000 лет назад Евклид привел изящное доказательство того, что их множество бесконечно.

Решето Эратосфена. Параллельные линии разных цветов, проходящие через таблицу из чисел, вычеркивают все числа, делимые на 3, 5, 7… и кратные им. Числа, через которые не проходит ни одна цветная полоса, являются простыми. Простые числа в начале полос в первом ряду заключены в круги. Четные числа не включены в таблицу, поскольку все они делятся на два

Тем не менее не существует простой волшебной формулы, по которой можно найти их все. Максимальные известные простые числа высоко ценятся математиками и криптографами, поскольку они используются для создания самых надежных в мире шифров. На данный момент максимальным известным простым числом является 230402457 – 1, в полной записи которого 9 152 052 цифры. Оно было найдено Кёртисом Коппером и его коллегами в 2005 году в рамках проекта GIMPS. Это математическая версия онлайн-проекта SETI. В нем используется центральный координирующий сервер, и любой, кто вложит вычислительную мощность своего компьютера в проект поиска простых чисел, получит некие большие числа, чтобы проверить, являются ли они простыми (подобно тому как онлайн-проект SETI передает радиосигналы из космоса, которые можно проанализировать на наличие признаков последовательностей, возможно, имеющих разумное начало). Некоммерческая организация Electronic Frontier Foundation учредила премию в миллион долларов тому, кто первым обнаружит простое число с 10 миллионами цифр. Поиски наибольших простых чисел в значительной мере продвигаются силами крупнейших компьютеров, и их скорость напрямую связана с развитием вычислительной мощности.

Хотя сейчас поиск новых простых чисел выполняется преимущественно с помощью быстрых компьютеров, были времена, когда их искали исключительно вручную с помощью человеческих рассуждений, которые ограничивали количество возможных вариантов. Первая и наиболее значительная процедура такого рода была разработана Эра-тосфеном (276-194 годы до нашей эры). Этот знаменитый математик родился в греческой колонии Кирена (сейчас это ливийский город Шаххат). Он возглавлял великую Александрийскую библиотеку и разработал методы для определения окружности Земли и расстояния от нее до Солнца и Луны.

Сведения о решете Эратосфена обнаружены в трактате «Введение в арифметику» сирийского математика Никомеда, написанном около 100 года нашей эры. Это было пособие для школьников гораздо проще «Начал» Евклида, благодаря чему оно широко использовалось вплоть до Средневековья как в Европе, так и в арабском мире. Предложенный Эратосфеном систематический процесс нахождения простых чисел посредством просеивания остальных сквозь решето является первым в математике алгоритмом. Он удобен, пока числа не становятся слишком большими. К сожалению, работы Эратосфена не сохранились и мы можем прочитать о решете только в трудах других авторов, свидетельствующих, что современники считали его великим энциклопедистом, хотя он и не был ведущим авторитетом ни в одной области. По этой причине его прозвали Бетой (В – вторая буква греческого алфавита), или Пентатлосом (так в те времена называли спортсменов-пятиборцев, которые отличились в состязаниях по сумме пяти дисциплин, но не стали чемпионами ни в одной из них в отдельности).

Никомед объясняет решето Эратосфена следующим образом: «Способ решета состоит в следующем. Все нечетные числа, начиная с тройки, последовательно располагаются в ряд, продолжаемый так далеко, насколько это возможно. Начав с первого из них, я смотрю, какие числа оно измеряет, и нахожу, что таковы числа, идущие через два, пока это можно проследить. И оно измеряет не случайно расположенные числа: первое из них отделено от него двумя промежуточными членами, и оно, в соответствии с количеством [единиц] в том числе, с которого начинается ряд, является троекратным; второе отделено от предыдущего еще двумя членами и является пятикратным; третье отделено от предыдущего еще двумя и является семикратным; четвертое отделено от предыдущего еще двумя и является девятикратным и так до бесконечности. <… > Начав заново, я смотрю, какие числа измеряет второе число, и нахожу, что все они отделены друг от друга четырьмя промежуточными членами. Первое из них, в соответствии с количеством [единиц] в том числе, с которого начинается ряд, является троекратным; второе согласно второму является пятикратным; третье согласно третьему является семикратным и так до бесконечности. <…> Ив целом ты можешь действовать так же… И те из них, которые ни разу не окажутся измеренными, но избегают этого, будут первичными и несоставными, просеянными с помощью решета».

Иначе говоря, решето работает так. Запишем все натуральные числа в строки по 10 десяток до максимального интересующего вас числа (назовем его N). Теперь вычеркнем все числа в сетке, которые не являются простыми по правилу Эратосфена. Во-первых, число

1 не считается простым, поэтому исключим его (если бы вы отнесли 1 к простым, в итоге пришлось бы вычеркнуть все числа в списке). Обведем в крут первое из оставшихся чисел –

2 – и вычеркнем последовательно все числа, кратные ему. Таким образом, будут исключены все четные числа. Обведем следующее число – 3 – и вычеркнем все оставшиеся кратные ему. Продолжим аналогичным образом, обводя первое оставшееся число и вычеркивая все кратные ему, которые сохранились к этому моменту. Числа, обведенные в круг, и будут простыми.

Вскоре вы обнаружите, что многие из чисел, намеченных для вычеркивания по причине делимости, например на 7, уже оказываются исключенными, поскольку делятся также на меньшее число (например, 21 = 3 х 7).

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

Наиболее усердным исследователем решета Эратосфена был американский математик Деррик Норман Лемер (1867-1938), опубликовавший таблицы факторизации для первых 10 миллионов простых чисел, выделенных из сетки всех натуральных чисел с помощью решета. Лемер ускорил этот утомительный процесс, частично его механизировав. Его сын построил машину, состоящую из вала, на котором были установлены 30 зубчатых колес со 100 зубьями. Эти колеса сцеплялись с 30 другими колесами с количеством зубьев, соответствующим одному из 30 простых чисел до 127. Вот как работал этот механизм: «Под каждым зубцом в этой второй группе колес находится небольшое отверстие. Когда машина настроена и готова к использованию, некоторые из этих отверстий закрыты, а некоторые – открыты. В сторону машины направляется луч света, после чего она приводится в движение электромотором. Все колеса главного вала вращаются с одинаковой скоростью, но колеса, сцепленные с ними, вращаются с различными скоростями из-за различного количества зубьев. Когда через сотни, а может, и тысячи оборотов одно отверстие каждого колеса оказывается в одной и той же точке в одно и то же время, иначе говоря, когда 30 отверстий выстраиваются в одну линию, луч света проходит сквозь всю машину, попадает на чувствительную фотоэлектрическую пластину и мгновенно останавливает машину. Небольшой счетчик, подсчитывающий количество оборотов главного вала, дает число, по которому легко можно определить все делители анализируемого большого числа».

Один из фактов, которые становятся очевидными при взгляде на изображение решета, заключается в том, что простые числа встречаются тем реже, чем больше они становятся. Это неудивительно. По мере увеличения чисел увеличивается и количество множителей, на которые они могут делиться: например, простым является каждое четвертое число в пределах сотни, каждое шестое число в пределах тысячи, одно из 12,7 в пределах миллиона и только одно из 19,8 в пределах миллиарда. Последовательность такова, что очень приблизительно одно из 2,3N чисел в пределах 10JV является простым. Это можно сказать и иначе: из чисел, меньших N, примерно одно из logN является простым, где logeN – натуральный логарифм JV26. Карл Фридрих Гаусс усовершенствовал эту теорию, предположив, что среди чисел, соседних с N, простым является примерно одно из 1 / logeiV, то есть приблизительно N logN чисел, меньших N, простые. Таким образом, при увеличении N через решето Эратосфена по-прежнему проходит достаточно много чисел. Криптографы не останутся без доступных простых чисел.