Книга: Рассказы о математике с примерами на языках Python и C

5. Простые числа

5. Простые числа

Каждый знает, что простые числа — такие числа, которые делятся только на единицу и самих себя. Но так ли они просты, как кажутся, и актуальны ли сегодня? Попробуем разобраться.

То, что существуют числа, которые не делятся ни на какое другое число, люди знали еще в древности. Последовательность простых чисел имеет следующий вид:

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …

Доказательство того, что этих чисел бесконечно много, дал еще Евклид, живший в 300 г. до н. э. Примерно в те же годы уже известный нам греческий математик Эратосфен, придумал довольно-таки простой алгоритм получения простых чисел, суть которого была в последовательном вычеркивании чисел из таблицы. Те оставшиеся числа, которые ни на что не делились, и были простыми. Алгоритм называется «решето Эратосфена» и за счет своей простоты (в нем нет операций умножения или деления, только сложение) используется в компьютерной технике до сих пор.

Видимо, уже во время Эратосфена стало ясно, что какого-либо четкого критерия, является ли число простым, не существует — это можно проверить лишь экспериментально. Существуют различные способы для упрощения процесса (например, очевидно, что число не должно быть четным), но простой алгоритм проверки не найден до сих пор, и скорее всего найден не будет: чтобы узнать, простое число или нет, надо попытаться разделить его на все меньшие числа.

Это несложно записать в виде программы на языке Python:

import math
def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
# Вывод всех простых чисел от 1 до N
N = 100
for p in range(1, N, 2):
    if is_prime(p): print(p)
# Вывод результата, является ли заданное число простым
print(is_prime(2147483647))

Желающие могут поэкспериментировать с программой самостоятельно.

Подчиняются ли простые числа каким-либо законам? Да, и они довольно любопытны. Так, например, французский математик Мерсенн еще в 16-м веке обнаружил, что много простых чисел имеет вид 2N - 1, эти числа названы числамиМерсенна. Еще незадолго до этого, в 1588 году, итальянский математик Катальди обнаружил простое число 2¹⁹ - 1 = 524287 (по классификации Мерсенна оно называется M19). Сегодня это число кажется весьма коротким, однако даже сейчас с калькулятором проверка его простоты заняла бы не один день, а для 16 века это было действительно огромной работой. На 200 лет позже математик Эйлер нашел другое простое число 2³¹ - 1 = 2147483647. Необходимый объем вычислений каждый может представить сам. Он же выдвинул гипотезу, названную позже «проблемой Эйлера», или «бинарной проблемой Гольдбаха»: каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел. Например, можно взять 2 любых четных числа: 123456 и 888777888. С помощью компьютера можно найти их сумму в виде двух простых чисел: 123456 = 61813 + 61643 и 888777888 = 444388979 + 444388909. Интересно здесь то, что точное доказательство этой теоремы не найдено до сих пор, хотя с помощью компьютеров она была проверена до чисел с 18 нулями.

Существует и другая теорема, называемая теоремой Ферма-Эйлера, открытая в 1640 году, которая говорит о том, что если простое число имеет вид 4 * k + 1, то оно может быть представлено в виде суммы квадратов других чисел. Так, например, в нашем примере простое число 444388909 = 4 * 111097227 + 1. И действительно, с помощью компьютера можно найти, что 444388909 = 19197 * 19197 + 8710*8710. Теорема была доказана Эйлером лишь через 100 лет.

И наконец Бернхардом Риманом в 1859 году была выдвинута так называемая «Гипотеза Римана» о количестве распределения простых чисел, не превосходящих некоторое число. Эта гипотеза не доказана до сих пор, она входит в список семи «проблем тысячелетия», за решение каждой из которых Математический институт Клэя в Кембридже готов выплатить награду в один миллион долларов США.

Так что с простыми числами не все так просто. Есть и удивительные факты. Например, в 1883 г. русский математик И. М. Первушин из Пермского уезда доказал простоту числа 2⁶¹ - 1 = 2305843009213693951. Даже сейчас компьютеру с запущенной вышеприведенной программой требуется несколько минут на проверку данного числа, а на то время это была поистине гигантская работа.

Кстати интересно, что существуют люди, обладающие уникальными способностями мозга — так например, известны аутисты, способные находить в уме (!) 8-значные простые числа. Как они это делают, непонятно. Такой пример описывается в книге известного врача-психолога Оливера Сакса «Человек, который принял жену за шляпу». По некоторым предположениям, такие люди обладают способностью «видеть» числовые ряды визуально, и пользуются методом «решета Эратосфена» для определения, является ли число простым или нет.

Еще одна интересная гипотеза была выдвинута Ферма, который предположил, что все числа вида

являются простыми. Эти числа называются «числами Ферма». Однако, это оказалось верным только для 5 первых чисел: F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65537. В 1732 году Эйлер опроверг гипотезу, найдя разложение на множители для F₅: F₅ = 641·6700417.

Существуют ли другие простые числа Ферма, пока неизвестно до сих пор. Такие числа растут очень быстро (для примера, F₇ = 340282366920938463463374607431768211457), и их проверка является непростой задачей даже для современных компьютеров.

Актуальны ли простые числа сегодня? Еще как! Простые числа являются основой современной криптографии, так что большинство людей пользуются ими каждый день, даже не задумываясь об этом. Любой процесс аутентификации, например, регистрация телефона в сети, банковские платежи и прочее, требуют криптографических алгоритмов. Суть идеи тут крайне проста и лежит в основе алгоритма RSA, предложенного еще в 1975 году. Отправитель и получатель совместно выбирают так называемый «закрытый ключ», который хранится в надежном месте. Этот ключ представляет собой, как, наверное, читатели уже догадались, простое число. Вторая часть — «открытый ключ», тоже простое число, формируется отправителем и передается в виде произведения вместе с сообщением открытым текстом, его можно опубликовать даже в газете. Суть алгоритма в том, что не зная «закрытой части», получить исходный текст невозможно.

К примеру, если взять два простых числа 444388979 и 444388909, то «закрытым ключом» будет 444388979, а открыто будут передано произведение 197481533549433911 (444388979 * 444388909). Лишь зная вторую половинку, можно вычислить недостающее число и расшифровать им текст.

В чем хитрость? А в том, что произведение двух простых чисел вычислить несложно, а вот обратной операции не существует — если не знать первой части, то такая процедура может быть выполнена лишь перебором. И если взять действительно большие простые числа (например, в 2000 символов длиной), то декодирование их произведения займет несколько лет даже на современном компьютере (к тому времени сообщение станет давно неактуальным). Гениальность данной схемы в том, что в самом алгоритме нет ничего секретного — он открыт и все данные лежат на поверхности (и алгоритм, и таблицы больших простых чисел известны). Сам шифр вместе с открытым ключом можно передавать как угодно, в любом открытом виде. Но не зная секретной части ключа, которую выбрал отправитель, зашифрованный текст мы не получим. Для примера можно сказать, что описание алгоритма RSA было напечатано в журнале в 1977 году, там же был приведен пример шифра. Лишь в 1993 году при помощи распределенных вычислений на компьютерах 600 добровольцев, был получен правильный ответ.

В завершение темы простых чисел, приведем вид так называемой «спирали Улама». Математик СтаниславУлам открыл ее случайно в 1963 году, рисуя во время скучного доклада на бумаге числовую спираль и отмечая на ней простые числа:

Как оказалось, простые числа образуют вполне повторяющиеся узоры из диагональных линий. В более высоком разрешении изображение выглядит так (картинка с сайта http://ulamspiral.com):

В общем, можно предположить что далеко не все тайны простых чисел раскрыты и до сих пор.

Оглавление книги