с высокой вероятностью достаточно быстро расшифровать любое сообщение.

В этом разделе мы обсуждаем вопрос о том, как искать большие простые числа.

Распределение простых чисел.

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

Определим функцию распределения простых чисел (prime distribution function) 7Г, положив 7г(п) равным количеству простых чисел, не превосходящих п. Например, на отрезке от 1 до 10 есть 4 простых числа 2, 3, 5 и 7, поэтому 7г(10) = 4.

Теорема 33.37 (асимптотический закон распределения простых чисел)

Выражение га/In га даёт неплохое приближение к 7г(га) даже при небольших значениях га. Уже при га = 109 (небольшое число с точки зрения специалистов по теории чисел) погрешность приближения не превосходит 6% (тг(109) = 50 847 478, 109/109 In 109 и 48 254 942).

Асимптотический закон позволяет оценить вероятность, с которой целое число, наугад выбранное из отрезка от 1 до га, является простым - это примерно 1/ In гг. Тем самым для отыскания простого числа от 1 до га нужно проверить на простоту порядка In га случайно выбранных чисел. Например, чтобы найти простое число из 100 десятичных знаков, надо перебрать пордяка In 10100 ~ 230 случайных чисел от 1 до 10100. (Эта оценка по очевидным причинам может быть уменьшена вдвое: проверять на простоту стоит только нечётные числа. Заметим также, что число десятичных знаков в наугад взятом числе от 1 до 10100 с большой вероятностью близко к 100 - около 90% всех чисел в этом диапазоне имеют 100 знаков, около 99% - 99 или более знаков, около 99, 9% - 98 или более знаков и т.д.)

Нам остаётся объяснить, каким образом можно проверить, будет ли простым данное большое число га. Другими словами, мы хотим

33.8. Проверка чисел на простоту

= 1.

п-»оо га/ In га

узнать, состоит ли разложение числа га на простые множители

ei еоег

п = Plp22 -р/,

(г 1; числа pi,p2,... ,рг - различные простые делители га) из единственного простого числа (г = 1, в\ = 1).

Самый простой способ проверки - перебор делителей (trial division). Будем пытаться разделить га на 2, 3,... , [\/п\ (чётные числа, большие 2, можно пропускать). Если га не делится ни на одно из этих чисел, то оно простое (если га разлагается в произведение двух или более множителей, то один из множителей не превосходит \/п). Но дело это долгое - уже число делений есть Q(\/n), и время работы экспоненциально зависит от длины записи числа га (напомним, что двоичное представление га занимает fi = [lg(ra+ 1)J битов, так что \/п = 0(2/2)). Таким образом, такой подход применим, лишь есть число га мало, или имеет небольшой делитель.

Если при переборе делителей мы обнаруживаем, что число га составное, то одновременно находится и делитель числа га. Для других способов проверки простоты это не так - можно убедиться, что число составное, так и не указав никакого его делителя. Это не удивительно, так как задача разложения числа на множители, по-видимому, гораздо сложнее задачи проверки простоты числа. К задаче разложения на множители мы вернёмся в следующем разделе.

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

Сейчас мы опишем «почти правильный» алгоритм проверки числа на простоту, приемлемый для многих практических приложений. (Небольшое усложнение этого алгоритма, делающее его совсем правильным, будет описано дальше.)

Обозначим через Z + множество всех ненулевых вычетов по модулю га:

Z+ = {l,2,...,ra-l}.

Если число га простое, то Z + = Z*.

Назовём число га псевдопростым по основанию a (base-a pseudo-prime), если выполнено утверждение малой теоремы Ферма:

an~l = 1 (mod га).(33.42)

Любое простое число га является псевдопростым по любому основанию a G Z+. Поэтому если нам удалось найти основание а, по которому га не является псевдопростым, то мы можем быть уверены, что га - составное. Оказывается, что во многих случаях достаточно проверить основание а = 2

Pseudoprime(п)

1if Modular-Exponentiation(2,n-l,n) \not\equiv 1 \pmod n

2then return composite(заведомо)

3else return prime(возможно)

Эта процедура может совершать ошибки, но только в одну сторону: если она сообщает, что число п составное, то это действительно так, но она может принять составное число за простое (если оно является псевдопростым по основанию 2). Как часто такое происходит? Оказывается, не так уж часто - среди чисел до 10 000 есть только 22 числа, для которых процедура Pseudoprime даёт неверный ответ (первые четыре из них - 341, 561, 645 и 1105). Можно показать, что доля таких «плохих» чисел среди /3-значных чисел стремится к 0 при fi -> оо. Используя оценки из работы Померанца [157], можно показать, что доля составных чисел среди 50-разрядных псевдопростых по основанию 2 чисел не превосходит 10 6, а среди 100-разрядных псевдопростых чисел - Ю-13.

Нет никаких причин ограничиваться проверкой лишь основания 2; можно проверять соотношение (33.42) и при других а. Но это не всегда помогает: существуют составные числа п, которые являются псевдопростыми по любому основанию а £ Z*. Такие числа называются числами Кармайкла (Carmichael numbers). Три первых числа Кармайкла таковы: 561, 1105 и 1729. Числа Кармайкла редки: среди первых ста миллионов положительных чисел их имеется всего 255. (В упр. 33.8-2 мы укажем одну из причин, по которым таких чисел мало.)

Сейчас мы исправим наш тест так, чтобы даже числа Кармайкла не смогли ввести его в заблуждение.

Вероятностный тест Миллера - Рабина

Этот вероятностный алгоритм проверки простоты числа получается из процедуры Pseudoprime двумя принципиальными усовершенствованиями.

•Тест Миллера - Рабина проверяет соотношение (33.42) для нескольких значений а.

•Вычисляя степень а, фигурирующую в сравнении (33.42), тест по ходу вычисления проверят, не обнаружился ли нетривиальный корень из 1 по модулю п. Если да, тест немедленно прекращает работу и сообщает, что число п - составное (следствие 33.35).

Процедура Miller-Rabin, приведённая ниже, ниже, получает на вход нечётное число п > 2 (простоту которого мы хотим проверить) и и целое положительное число s, определяющее, сколько итераций надо провести (чем больше s, тем меньше вероятность ошибки). Тест использует генератор случайных чисел Random (см. раздел 8.3); процедура Random(1,ti - 1) возвращает случайное целое число а, равномерно распределённое на отрезке 1 а п - 1.

Тест использует процедуру Witness: Witness(<2, п) истинно, если а является «свидетелем» того, что число п составное.

Witness(а,п)

1 пусть \langle b k,b {k-l},\ldots,b 0$ --- двоичная запись $п-1$