ЗАРОЖДЕНИЕ КРИПТОГРАФИИ
         

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


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

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

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

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


Следующая функция, определенная на множестве целых чисел,

является характером по модулю и порядок этого характера равен . Сумма

называется суммой Гаусса. Формулируемая ниже теорема 3 представляет собой аналог малой теоремы Ферма, используемый в алгоритме Адлемана - Ленстры.

Теорема 5.   Пусть  - нечетное простое число, . Тогда в кольце

выполняется сравнение

Если при каких-либо числах сравнение из теоремы 3 нарушается, можно утверждать, что составное число. В противном случае, если сравнение выполняется, оно дает некоторую информацию о возможных простых делителях числа . Собрав такую информацию для различных , в конце концов удается установить, что имеет лишь один простой делитель и является простым.

В случае легко проверить, что сравнение из теоремы 3 равносильно хорошо известному в элементарной теории чисел сравнению



(13)
где  - так называемый символ Якоби. Хорошо известно также, что последнее сравнение выполняется не только для простых , но и для любых целых , взаимно простых с . Заметим также, что для вычисления символа Якоби существует быстрый алгоритм, основанный на законе взаимности Гаусса и, в некотором смысле, подобный алгоритму Евклида вычисления наибольшего общего делителя. Следующий пример показывает, каким образом выполнимость нескольких сравнений типа () дает некоторую информацию о возможных простых делителях числа .

Пример 1.   (Х. Ленстра). Пусть  - натуральное число, , для которого выполнены сравнения

(14)
а кроме того с некоторым целым числом имеем

(15)
Как уже указывалось, при простом сравнения () выполняются для любого , взаимно простого с , а сравнение () означает, что есть первообразный корень по модулю . Количество первообразных корней равно , т.е. достаточно велико. Таким образом, число с условием () при простом может быть найдено достаточно быстро с помощью случайного выбора и последующей проверки ().

Докажем, что из выполнимости (14-15) следует, что каждый делитель числа удовлетворяет одному из сравнений




(16)
Не уменьшая общности, можно считать, что  - простое число. Введем теперь обозначения , , где и  - нечетные числа. Из (15) и сравнения следует, что . Далее, согласно (), выполняются следующие сравнения

означающие (в силу того, что символ Якоби может равняться лишь или ), что

При k$" width="48" height="29" > это равенство означает, что при , и, следовательно,

. Если же , то имеем и . Этим () доказано.

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

Опишем (очень грубо) схему алгоритма Адлемана - Ленстры для проверки простоты :


1) выбираются различные простые числа и различные простые нечетные такие, что

а) для каждого все простые делители числа содержатся

среди и не делятся на квадрат простого числа,

б) \sqrt{N} $" width="163" height="37" >;

2) для каждой пары выбранных чисел , проводятся тесты, подобные сравнению из теоремы 3. Если не удовлетворяет какому-либо из этих тестов - оно составное. В противном случае

3) определяется не очень большое множество чисел, с которыми только и могут быть сравнимы простые делители . А именно, каждый простой делитель числа должен удовлетворять сравнению вида


4) проверяется, содержит ли найденное множество делители . Если при этом делители не обнаружены, утверждается, что  - простое число.

Если число составное, оно обязательно имеет простой делитель , меньший

Пример 2.  

Если выбрать следующие множества простых чисел

то таким способом удается проверять простоту чисел

Отметим, что в работе [] для тестирования использовались не сравнения теоремы 3, а закон взаимности для степенных вычетов и так называемые суммы Якоби. Сумма Якоби


определяется для двух характеров по модулю . Если характеры имеют порядок , то соответствующая сумма Якоби принадлежит кольцу . Поскольку числа , участвующие в алгоритме, сравнительно невелики, то вычисления с суммами Якоби производятся в полях существенно меньшей степени, чем вычисления с суммами Гаусса. Это главная причина, по которой суммы Якоби предпочтительнее для вычислений. При выполняется классическое соотношение




связывающее суммы Гаусса с суммами Якоби и позволяющее переписать сравнение теоремы 3 в терминах сумм Якоби (см. [
]). Так, при и соответствующее сравнение, справедливое для простых , отличных от 2, 3, 7, принимает вид

где и  - некоторый корень кубический из 1.

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

и взяв равным произведению простых чисел с условием, что делится на , получим 1{,}5\cdot10^{52} $" width="97" height="33" >, что позволяет доказывать простоту чисел , записываемых сотней десятичных знаков. При этом вычисления будут проводиться в полях, порожденных корнями из 1 степеней 16, 9, 5 и 7.

Мой персональный компьютер с процессором Pentium-150, пользуясь реализацией этого алгоритма на языке UBASIC, доказал простоту записываемого 65 десятичными знаками, большего из простых чисел в примере Ривеста, Шамира и Адлемана (см. раздел ) за 8 секунд. Сравнение этих 8 секунд и 17 лет, потребовавшихся для разложения на множители предложенного в примере числа, конечно, впечатляет.

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

арифметических операций. А в предположении эта оценка сложности может быть получена при эффективно указанных и .

Next: 4.7. Как раскладывают составные

Up: 4. Алгоритмические проблемы теории

Previous: 4.5. Как строить большие

Contents:



Содержание раздела