Как проверить большое число на простоту
Есть некоторое отличие в постановках задач предыдущего и настоящего разделов. Когда мы строим простое число , мы обладаем некоторой дополнительной информацией о нем, возникающей в процессе построения. Например, такой информацией является знание простых делителей числа . Эта информация иногда облегчает доказательство простоты .
В этом разделе мы предполагаем лишь, что нам задано некоторое число , например, выбранное случайным образом на каком-то промежутке, и требуется установить его простоту, или доказать, что оно является составным. Эту задачу за полиномиальное количество операций решает указанный в разделе алгоритм Миллера. Однако, справедливость полученного с его помощью утверждения зависит от недоказанной . Если число выдержало испытания для 100 различных значений параметра , то, по-видимому, можно утверждать, что оно является простым с вероятностью большей, чем . Эта вероятность очень близка к единице, однако все же оставляет некоторую тень сомнения на простоте числа . В дальнейшем в этом разделе мы будем считать, что заданное число является простым, а нам требуется лишь доказать это.
В настоящее время известны детерминированные алгоритмы различной сложности для доказательства простоты чисел. Мы остановимся подробнее на одном из них, предложенном в 1983 г. в совместной работе Адлемана, Померанца и Рамели []. Для доказательства простоты или непростоты числа этот алгоритм требует арифметических операций. Здесь - некоторая положительная абсолютная постоянная. Функция хоть и медленно, но все же возрастает с ростом , поэтому алгоритм не является полиномиальным. Но все же его практические реализации позволяют достаточно быстро тестировать числа на простоту. Существенные усовершенствования и упрощения в первоначальный вариант алгоритма были внесены в работах Х.Ленстры и А.Коена [,]. Мы будем называть описываемый ниже алгоритм алгоритмом Адлемана - Ленстры.
В основе алгоритма лежит использование сравнений типа малой теоремы Ферма, но в кольцах целых чисел круговых полей, т.е. полей, порожденных над полем числами - корнями из . Пусть - простое нечетное число и - первообразный корень по модулю , т.е. образующий элемент мультипликативной группы поля , которая циклична. Для каждого целого числа , не делящегося на , можно определить его индекс, , называемый также дискретным логарифмом, с помощью сравнения . Рассмотрим далее два простых числа с условием, что делится на , но не делится на .
Следующая функция, определенная на множестве целых чисел,
является характером по модулю и порядок этого характера равен . Сумма
называется суммой Гаусса. Формулируемая ниже теорема 3 представляет собой аналог малой теоремы Ферма, используемый в алгоритме Адлемана - Ленстры.
Теорема 5. Пусть - нечетное простое число, . Тогда в кольце
выполняется сравнение
Если при каких-либо числах сравнение из теоремы 3 нарушается, можно утверждать, что составное число. В противном случае, если сравнение выполняется, оно дает некоторую информацию о возможных простых делителях числа . Собрав такую информацию для различных , в конце концов удается установить, что имеет лишь один простой делитель и является простым.
В случае легко проверить, что сравнение из теоремы 3 равносильно хорошо известному в элементарной теории чисел сравнению
| (13) |
Пример 1. (Х. Ленстра). Пусть - натуральное число, , для которого выполнены сравнения
| (14) |
| (15) |
Докажем, что из выполнимости (14-15) следует, что каждый делитель числа удовлетворяет одному из сравнений
| (16) |
означающие (в силу того, что символ Якоби может равняться лишь или ), что
При 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:
