Введение в криптографию
[an error occurred while processing this directive]

Как проверить большое число на простоту


Есть некоторое отличие в постановках задач предыдущего и настоящего разделов. Когда мы строим простое число , мы обладаем некоторой дополнительной информацией о нем, возникающей в процессе построения. Например, такой информацией является знание простых делителей числа . Эта информация иногда облегчает доказательство простоты .

В этом разделе мы предполагаем лишь, что нам задано некоторое число , например, выбранное случайным образом на каком-то промежутке, и требуется установить его простоту, или доказать, что оно является составным. Эту задачу за полиномиальное количество операций решает указанный в разделе  алгоритм Миллера. Однако, справедливость полученного с его помощью утверждения зависит от недоказанной . Если число выдержало испытания для 100 различных значений параметра , то, по-видимому, можно утверждать, что оно является простым с вероятностью большей, чем . Эта вероятность очень близка к единице, однако все же оставляет некоторую тень сомнения на простоте числа . В дальнейшем в этом разделе мы будем считать, что заданное число  является простым, а нам требуется лишь доказать это.

В настоящее время известны детерминированные алгоритмы различной сложности для доказательства простоты чисел. Мы остановимся подробнее на одном из них, предложенном в 1983 г. в совместной работе Адлемана, Померанца и Рамели []. Для доказательства простоты или непростоты числа этот алгоритм требует арифметических операций. Здесь  - некоторая положительная абсолютная постоянная. Функция хоть и медленно, но все же возрастает с ростом , поэтому алгоритм не является полиномиальным. Но все же его практические реализации позволяют достаточно быстро тестировать числа на простоту. Существенные усовершенствования и упрощения в первоначальный вариант алгоритма были внесены в работах Х.Ленстры и А.Коена [,]. Мы будем называть описываемый ниже алгоритм алгоритмом Адлемана - Ленстры.

В основе алгоритма лежит использование сравнений типа малой теоремы Ферма, но в кольцах целых чисел круговых полей, т.е. полей, порожденных над полем числами  - корнями из . Пусть  - простое нечетное число и - первообразный корень по модулю , т.е. образующий элемент мультипликативной группы поля , которая циклична. Для каждого целого числа , не делящегося на , можно определить его индекс, , называемый также дискретным логарифмом, с помощью сравнения . Рассмотрим далее два простых числа с условием, что делится на , но не делится на .




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]