Он, разумеется, не сознавал, насколько важной станет эта задача в эпоху интернета и электронной торговли. Пока что никто, в том числе и сам великий Гаусс, не придумал шортката к нахождению простых делителей крупных чисел. Количество простых чисел, которые нужно перебрать, чтобы расшифровать 200-значное число, так велико, что любая такая попытка будет абсолютно нецелесообразной. Мы предполагаем, что задача факторизации – выражения числа в виде произведения меньших чисел – может быть сложной по самой своей природе. Это один из нерешенных вопросов, над которыми работают сейчас математики. Сможем ли мы доказать, что шортката к нахождению простых чисел не существует?

Но погодите. Как же тогда расшифровывает сообщения сам веб-сайт? Дело в том, что он начинает выполнение этого алгоритма с выбора двух простых чисел приблизительно по 100 знаков каждое, а затем перемножает их для получения 200-значного кодового числа. Простые числа, позволяющие произвести это вычисление в обратном порядке, известны только веб-сайту, и никому другому.

Тем не менее нахождение простых чисел – это одна из задач, которые математики еще не решили. Секрет расположения простых чисел в численной вселенной, так называемая гипотеза Римана, также входит в число семи Задач тысячелетия. Но, хотя на самом деле математики не понимают, как распределены простые числа, у нас есть один интересный шорткат, помогающий находить большие простые числа для таких интернет-кодов. Он основывается на свойстве простых чисел, которое открыл великий французский математик XVII века Пьер де Ферма. Он доказал, что если p – простое число, то результат возведения любого числа n, меньшего p, в степень p делится на p с остатком, равным n. Например, 2⁵ = 32, а остаток от деления 32 на 5 равен 2.

Следовательно, если я хочу проверить, простое ли число, например, q, то обнаружение числа, меньшего q, для которого это правило не выполняется, означает, что q – число составное. Например, 2⁶ = 64, а остаток от деления 64 на 6 равен 4, а не 2. Значит, число 6 не может быть простым, потому что оно не проходит тест Ферма. Этот тест был бы не слишком полезным, если бы, скажем, существовало лишь одно число, меньшее q, для которого это условие не выполнялось бы. В таком случае, возможно, пришлось бы перебрать все числа, меньшие q, – а тогда с тем же успехом можно было бы прямо проверить число q на неделимость. Великое достоинство этого теста состоит в том, что если потенциальный кандидат в простые числа его проваливает, то проваливает он его с треском. При применении уловки Ферма оказывается, что более половины чисел, меньших q, свидетельствуют, что q – число не простое.