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

Грасиан Энрике

Псевдопростые числа

В тестах простоты наиболее часто используется малая теорема Ферма. Напомним, что эта теорема гласит: «Если р — простое число, то не существует такого числа а у меньшего р (а и р взаимно просты), что a^p-1—1 дает при делении на р отличный от нуля остаток».

Теорема имеет ограничения, поскольку, как мы видели, она дает необходимое, но не достаточное условие. Например, если взять р = 7, мы видим, что З⁶ — 1

делится на 7. Нет никакой гарантии, что 7 — простое число (мы-то знаем, что это простое число, потому что взяли для примера небольшие числа, но мы должны представить, что имеем дело с большими числами). Однако если взять р = 8, мы видим, что при делении З⁷ — 1 на 8 получается 273,25, а значит, остаток не ноль. Теперь мы уверены, что 8 — не простое число (не находя его делителей).

Мы знаем точно, что любое число, которое не проходит тест с данным основанием а у является составным.

С другой стороны, если число проходит тест и является простым, мы называем основание «ложным». И продолжаем тестирование. Вероятность обнаружения «ложных» чисел уменьшается на 1/2 с каждым тестом, так что вероятность того, что число является простым, продолжает расти.

Число р, которое, не являясь простым, проходит тест с основанием а, называется псевдопростым для этого основания. Можно дать более общее определение псевдопростого числа: число называется псевдопростым, если оно проходит тест простоты, но оказывается составным.

Дело обстоит сложнее для чисел, которые проходят тесты с любым основанием, но не являются простыми. Например, число 561 проходит тест простоты с любым основанием и все же является составным (561 = 3 х 11 х 17). Такие числа, открытые американским математиком Робертом Кармайклом (1879–1967), называются числами Кармайкла. Сегодня известно 2163 числа Кармайкла, и они находятся среди первых 25 млрд натуральных чисел. Все они имеют по крайней мере три простых делителя.

Существует 16 чисел Кармайкла, меньших 100 000, а именно:

561,1105,1729, 2465, 2821, 6601, 8911,10585,15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361.

Числа Кармайкла также называют абсолютными псевдопростыми числами.

Тесты простоты

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

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

Наиболее широко используется так называемый «тест Миллера — Рабина», версия теста простоты Ферма, основанная на гипотезе Римана. Это вероятностный полиномиальный алгоритм, но вероятность ошибки составляет от 1/10₈₀ до 1/10⁵⁰, поэтому на практике он может считаться вполне точным.

6 августа 2002 г. три исследователя из технологического института в Канпуре (Индия), Маниндра Агравал, Нирадж Каял и Нитин Саксена, опубликовали полиномиальный детерминированный тест простоты на основе обобщения малой теоремы Ферма:

Несмотря на это, наиболее часто используемым методом по-прежнему является вероятностный полиномиальный алгоритм — в силу своего быстродействия.

Большинство веб-браузеров включает алгоритм шифрования, который может использовать такой метод для поиска больших простых чисел до 2048 битов.

Сегодня используются три криптографических системы: RSA, DSA (Digital Signature Algorithm, алгоритм цифровой подписи), и ECDSA (Elliptical Curve Digital Signature Algorithm, алгоритм цифровой

подписи на эллиптических кривых). Ни один эксперт не сомневается в безопасности, предоставляемой каждой из этих трех систем. Разница между ними заключается в кодах, которые они используют: безопасность, которую обеспечивают 2048-битные коды в первых двух, эквивалентна использованию 224 битов в третьей, при этом время вычислений значительно уменьшается. В то время как в первых двух используются субэкспоненциальные алгоритмы, в третьей применяется экспоненциальный тип, что дает лучшие результаты.

* * *

ДИКОВИННЫЕ ЧИСЛА

Число 313 изображено на номерном знаке автомобиля Дональда Дака. Оно обладает любопытным свойством палиндрома: его можно читать слева направо и справа налево как в десятичной системе счисления, так и в двоичной. Это единственное трехзначное простое число с таким свойством: 313 (в десятичной системе) = 100111001 (в двоичной системе). Кроме того, число 100111001 в десятичной системе счисления является простым.

Существует много простых чисел со странными свойствами. Например, «репьюниты» (от repeated unit — «повторенная единица»), которые состоят из длинных последовательностей единиц. Число 11111111111111111111111 (двадцать три единицы) является простым. В принципе, это просто диковинки, хотя в один прекрасный день эти числа могут стать частью теоремы или гипотезы, имеющей некую ценность в математике. Еще одна любопытная последовательность основана на числе 91, которое является составным (91–13 x 7). Если в середину этого числа вставлять последовательности нулей и девяток, то полученные числа чередуются, являясь то простыми, то составными:

9901 — простое;

999001 — составное;

99990001-простое;

9999900001 — составное;

999999000001 — простое;

99999990000001 — составное;

9999999900000001 — простое;

999999999000000001 — составное.

К сожалению, следующее число 999999999990000000001 также является составным!

* * *

Продолжение следует…

Мы видели, как математики, такие как Мерсенн, Ферма, а иногда даже сам Эйлер, искали практические инструменты для работы с числами. Это в некоторой степени подрывало становление строгой теории. Доказательства едва упоминались, но результаты продолжали использоваться. Гаусс начал новую эру в истории математики, настояв на том, что приведение строгих доказательств должно быть главной целью.

Тем не менее с простыми числами мы снова, казалось бы, опираемся на эмпирический подход. Мы используем недоказанные теоремы и полагаемся на результаты, если знаем, что вероятность ошибки очень мала. Мы действуем как Ферма, но даже не пытаемся прятать гипотетические доказательства. Мы можем так делать, потому что, во-первых, имеем огромные возможности благодаря компьютерным алгоритмам, а во-вторых — огромную потребность в больших простых числах.

В чисто теоретическом смысле можно сказать, что простые числа продолжают сопротивляться усилиям математиков. История их исследований в значительной степени является историей неудач. Наибольший успех был с дзета-функцией Римана, но мы все-таки понимаем, что это лишь частичный успех. Эйлер, который был великим математическим провидцем, не испытывал особенно оптимистичных чувств по поводу наших шансов понять эти неуловимые числа: «Математики уже давно тщетно пытаются найти закономерности в последовательности простых чисел, но у меня есть основания полагать, что это тайна, в которую человеческий разум никогда не сможет проникнуть».

Приложение

Доказательства

1. Доказательство основной теоремы арифметики

Теорема утверждает, что любое натуральное число, отличное от 1, может быть единственным способом выражено в виде произведения простых чисел. Сначала мы должны объяснить, почему единица не считается простым числом.

Существует несколько причин, но наиболее очевидным является тот факт, что для числа 1 теорема не имеет места, так как оно может быть разложено на множители несколькими способами: