Раздел шестой

1. Построение больших простых чисел.

Криптографические приложения требуют больших простых чисел. Поэтому методы построения последних чрезвычайно важны. В простейшем случае дело обстоит так: надо взять некоторое натуральное число и подвергнуть его проверке на простоту, В случае, если проверка успешно пройдена, то число найдено. Таким образом, востребованными оказываются способы проверки простоты, которые называются тестами на простоту. Приведем пример простейшего теста.

Вход: .

Положить .

1. Если , то продолжать. Иначе закончить с резолюцией «простое».

2. Вычислить .

3. Если , то закончить с резолюцией «составное».

4. Если , то увеличить k на единицу и вернуться к выполнению п.1.

Ясно, что в случае, когда число n составное, процесс проверки может закончиться очень быстро. Например, если n – четное или кратно какому-либо малому простому числу. Но если n – число простое, то придется сделать шагов. Конечно, границу для k в п.1 можно уменьшить до , руководствуясь

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

Наименьший простой делитель составного числа n не превосходит .

Но и тогда алгоритм остается экспоненциальным, т.е. время его работы может составить .

Другим известным способом определения простоты числа является решето Эратосфена (около 250 г. до н. э.). Этот алгоритм позволяет на основе указанного выше результата получить список всех простых чисел , если располагать подобным списком для простых . Для своей реализации на ЭВМ этот метод требует очень большого объема памяти, а время его работы можно оценить величиной . Оба метода работают очень медленно, и для нужд криптографии неприменимы.

До последнего времени (2003 г.) неизвестны были детерминированные полиномиальные тесты на простоту. Лучший из апробированных тестов являлся квазиполиномиальным, ибо его время работы оценивается величиной

.

Этот алгоритм способен различать простые числа порядка и выше за приемлемое время. Иное дело – вероятностные тесты простоты.

2. Псевдопростые числа и вероятностные тесты на простоту.

Определение. Пусть n – нечетное составное число и пусть b – любое целое такое, что (n , b) = 1. Тогда n называется псевдопростым Ферма, или просто псевдопростым, по основанию b, если выполняется сравнение

b 1 (mod n). (6.1)

Пример. Число n = 91 является псевдопростым по основанию 3, так как справедливо сравнение: 3 1 (mod 91). Однако 91 не является псевдопростым по основанию 2, ибо 2 64 (mod 91). Если не знать, что 91 есть составное число, то последнее сравнение убеждает в этом ( ).

Из определения псевдопростого числа видно, что оно в определенном смысле похоже на простое. Именно, для простых n соотношение (6.1) выполняется всегда в силу известной малой теоремы Ферма. Эта теорема могла бы служить основанием для теста на простоту, если бы не «мешали» псевдопростые. Имеет место следующая теорема.

Теорема. Существует бесконечно много псевдопростых чисел Ферма для любого основания b.

Определение. Числом Кармайкла называется составное число, для которого сравнение (6.1) выполняется для любого числа b (Z/nZ)*.

Пример. Число n = 561 = 3 11 17 есть число Кармайкла. Можно показать, что это есть наименьшее число Кармайкла.

Пример. Числами Кармайкла, меньшими 100000, являются: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973 и 75361.

Замечание. Недавно (1992 г.) было доказано, что множество чисел Кармайкла

бесконечно.

Определение. Если n – нечетное составное число и b – такое целое число, что

(n , b) = 1 и выполняется сравнение

b (modn), (6.2)

то n называется псевдопростым числом Эйлера по основанию b.

Теорема. Если n есть псевдопростое число Эйлера по основанию b, то оно является псевдопростым Ферма по основанию b.

Доказательство. Достаточно возвести в квадрат обе части сравнения (6.2).

Пример. Утверждение, обратное теореме, неверно. В примере число 91 было псевдопростым по основанию 3. Однако,

3 27 (mod 91)

и, значит, (6.2) не выполняется для n = 91, b = 3. Примером основания, по которому 91 является псевдопростым Эйлера, есть 10. Действительно, 10 (mod 91) и

.

Отметим, что для псевдопростых Эйлера нет аналога чисел Кармайкла. Каждое составное число n не выдерживает тест (6.2) для по крайней мере половины всех возможных оснований b. Точнее, имеет место

Теорема. Для нечетного n 3 положим

S = (Z )* | (mod n) .

Если n составное, то |S | , где – функция Эйлера.

Доказательство. По мультипликативности символа Якоби S является подгруппой мультипликативной группы (Z )*. Чтобы доказать теорему, достаточно проверить, что эта подгруппа собственная. Действительно, по теореме Лагранжа |S | делит |(Z )*| = (n), а поэтому, если эти числа не равны между собой, то |S | может быть не более (n) / 2. Таким образом, остается доказать, что существует элемент у (Z )* \ S .

Предположим для начала, что n свободно от квадратов, т.е. в разложении n = p … p на простые множители каждое число встречается лишь один раз. Выберем в (Z )* квадратичный невычет s по модулю р . По китайской теореме об остатках в (Z )* существует у такое, что

у s (mod p ), y 1 (mod p … p ). (6.3)

Для такого у имеем

= = = (-1)1 = - 1.

Но у – 1 (mod n), так как было бы у - 1 (mod p … p ) в противоречие с условиями (4.3).

Теперь предположим, что существует простое р такое, что р | n. Выберем элемент у = 1+n / p. Ясно, что для каждого простого делителя q числа n выполняется сравнение у 1 (mod q). Это означает, что у (Z )* и вследствие мультипликативности символа Якоби

= 1.

С другой стороны, у 1 (mod n). Действительно,

у = (1+ n / p) = 1 + (mod n)

(остальные члены в биноме Ньютона кратны n). Таким образом, если бы левая часть была равна 1 по модулю n, то выполнялось бы сравнение

0 (mod n).

А это возможно лишь при условии, что р | (n – 1)/ 2, что невозможно, ибо p | n.

Тест Соловея-Штрассена. На последней теореме основан вероятностный тест на простоту, который выдерживают простые числа с вероятностью 1, а составные – с вероятностью менее ½. Время работы оценивается величиной

О (log n), где n – тестируемое число.

Вход: нечетное n.

1. Выбрать случайное х такое, что 1 < x < n .

2. Если (x , n) 1, то прекратить работу с резолюцией «составное». Иначе продолжать.

3. Если x (mod n), то остановиться с резолюцией «составное», иначе остановиться с резолюцией «простое».

Определение. Пусть n – нечетное составное число, и пусть n – 1 = 2 t, где число t является нечетным. Пусть b (Z/ nZ)*. Если числа b и n связаны условием

b 1 (mod n) или

существует число r, 0 r < s, такое, что b -1 (mod n), (6.4)

то число n называется сильно псевдопростым по основанию b.

Пример. Примерами сильно псевдопростых чисел являются:

– сильно псевдопростое по основанию 7;

781 – сильно псевдопростое по основанию 5;

2047 – сильно псевдопростое по основанию 2.

Теорема. Если n есть сильно псевдопростое число по основанию b, то оно является и псевдопростым числом Эйлера по основанию b.

Замечание. Утверждение, обратное теореме 7, неверно.

Теорема. Если n есть нечетное составное число, то n является сильно псевдопростым по основанию b для не более чем 1/4 таких оснований b, где 0 < b < n.

Тест Миллера-Рабина. На теореме 4.9 и понятии сильно псевдопростого числа основан тест на простоту, который с вероятностью 1 подтверждает простоту числа и с вероятностью менее ¼ ошибается, называя простым число составное. Время работы этого теста оценивается величиной О( , где n – тестируемое число.

Вход: n – нечетное натуральное число, где нечетное.

1. Выбрать случайное х такое, что

2. Если ( то остановиться с резолюцией «n – составное», иначе продолжать.

3. Вычислить

4. Если то остановиться с резолюцией «простое», иначе продолжать.

5. Вычислять пока не выявится, что , .

6. Если то остановиться с резолюцией “простое”, а иначе – остановиться с резолюцией «составное».

Замечания:

1. При проверке чисел на простоту не всегда нужно ожидать, если есть подозрение, что проверяемое является сильно псевдопростым, что придется иметь дело с очень большими основаниями, по которым это число и является сильно псевдопростым. Например, вычислено, что для чисел не больших 2,5 существует лишь одно число, а именно 3215031751, которое является сильно псевдопростым по основаниям 2,3,5 и 7. Можно привести и другие результаты такого вида, скажем, если и проходит тест Миллера-Рабина по основаниям 2, 3, 5, 7, 11, и 13, то n – простое; если и проходит тест Миллера-Рабина по основаниям 2, 13, 23 и 1662803, то n – число простое.

2. Вероятностные тесты на простоту не дают полной уверенности в том, что число, прошедшее тест, действительно простое. Желательно иметь, например, такой результат: существует некоторое сравнительно небольшое число В (зависящее от n) такое, что если n – составное, то существует определенное основание b < B, для которого число n не является сильно псевдопростым. Тогда применение вероятностного теста Миллера-Рабина только для первых В оснований вычислительно доказывало бы простоту числа n или противоположное утверждение.

Такой результат известен, но он зависит от уже упоминавшейся недоказанной пока т.н. расширенной гипотезы Римана (РГР). Его можно сформулировать так:

Если справедлива РГР и n – составное нечетное число, то n не проходит тест Миллера-Рабина для по крайней мере одного основания b, где

Общая схема построения простого числа заданного размера выглядит так: Выбирается случайное натуральное число n такое, что . Это число проходит проверку на делимость на «малые» простые числа, т.е. на числа 2, 3, 5, 7 т.д.

Массив «малых» простых чисел может быть весьма значительным по размеру. Затем наступает очередь вероятностных тестов. Они работают быстро и могут выявить, что испытуемое число является составным. Если, например, тест Миллера-Рабина принимает вход при некотором количестве испытаний, то наступает черед детерминированных тестов, которые дадут окончательный ответ. Продемонстрируем один из возможных способов построения большого простого числа, на основании уже имеющегося простого.

3. Один метод построения простых чисел.

Метод основан на модифицированной теореме Ферма.

Теорема. Пусть – нечетные натуральные числа, , причем для каждого простого делителя q числа S существует целое число а такое, что

.

Тогда каждый простой делитель р числа N удовлетворяет сравнению .

Доказательство. Пусть р – простой делитель числа N, а q – некоторый простой делитель S. Из условий теоремы следует, что в поле F справедливы соотношения

Обозначим через r порядок элемента а в F . Первые два из последних соотношений означают, что q входит в разложение на простые множители числа r в такой же степени, как и в разложение N-1, а последнее – что р-1 делится на r. Таким образом, каждый простой делитель числа S входит в разложение р-1 в степени не меньшей, чем в S. Значит, р-1 делится на S. Для завершения доказательства заметим, что р-1 четно. Следствие. Если выполнены условия теоремы и , то N – простое число. Действительно, если N равняется произведению не менее двух простых чисел, то каждое из них, согласно утверждению теоремы, не меньше . Но тогда

.

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

Пусть теперь известно некоторое простое число S. Опираясь на него будем строить новое простое число N. Выберем для этого случайное четное число R в промежутке и положим . Протестируем число N на простоту путем деления на малые делители и вероятностными тестами. Если при этом выявится, что N составное, то следует выбирать новое число R и повторить вычисления. Если такого не произошло, то можно попытаться доказать простоту N при помощи доказанной теоремы. Для этого случайным образом выбирают число а, 1< a < N, и проверяют для него выполнимость соотношений:

.

Если выбранное а удовлетворяет указанным соотношениям, то по следствию из последней теоремы число N – простое. Если соотношения не выполняются, то следует выбирать другое число а, и так до тех пор, пока соответствующее а не будет найдено.