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

Next: 4.7. Как раскладывают составные Up: 4. Алгоритмические проблемы теории Previous: 4.5. Как строить большие Contents: Содержание

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

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

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

В настоящее время известны детерминированные алгоритмы различной сложности для доказательства простоты чисел. Мы остановимся подробнее на одном из них, предложенном в 1983 г. в совместной работе Адлемана, Померанца и Рамели [13]. Для доказательства простоты или непростоты числа этот алгоритм требует $(\ln N)^{c\ln\!\ln\!\ln N}$ арифметических операций. Здесь - некоторая положительная абсолютная постоянная. Функция $\ln\ln\ln N$ хоть и медленно, но все же возрастает с ростом , поэтому алгоритм не является полиномиальным. Но все же его практические реализации позволяют достаточно быстро тестировать числа на простоту. Существенные усовершенствования и упрощения в первоначальный вариант алгоритма были внесены в работах Х.Ленстры и А.Коена [14,15]. Мы будем называть описываемый ниже алгоритм алгоритмом Адлемана - Ленстры.

В основе алгоритма лежит использование сравнений типа малой теоремы Ферма, но в кольцах целых чисел круговых полей, т.е. полей, порожденных над полем $\QQ$ числами $\zeta_p=e^{2\pi i/p}$ - корнями из . Пусть - простое нечетное число и - первообразный корень по модулю , т.е. образующий элемент мультипликативной группы поля $\FF_q$ , которая циклична. Для каждого целого числа , не делящегося на , можно определить его индекс, $\ind_q x\in\ZZ/(q-1)\ZZ$ , называемый также дискретным логарифмом, с помощью сравнения $x\equiv c^{\ind_qx}\pmod q$ . Рассмотрим далее два простых числа с условием, что делится на , но не делится на .

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

$\begin{displaymath} \chi(x)=\left\{ \begin{aligned} 0,&&\text{ если }&& q&\ver... ...^{\ind_qx},&&\text{ если }&& (x,q&)=1 \end{aligned} \right. \end{displaymath}$

является характером по модулю

и порядок этого характера равен

. Сумма

$\begin{displaymath} \tau(\chi)=-\sum\limits_{x=1}^{q-1}\chi(x)\zeta_q^x\in\ZZ[\zeta_p,\zeta_q] \end{displaymath}$

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

Теорема 5. Пусть - нечетное простое число, . Тогда в кольце $\ZZ[\zeta_p,\zeta_q]$ выполняется сравнение

$\begin{displaymath} \tau(\chi)^N\equiv \chi(N)^{-N}\cdot \tau(\chi^N)\pmod{NZ[\zeta_p,\zeta_q]}. \end{displaymath}$

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

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

$\begin{displaymath} q^{\frac{N-1}{2}}\equiv\genfrac{(}{)}{}{0}{q}{N}\pmod N, \end{displaymath}$ (13)

где $\genfrac{(}{)}{}{0}{q}{N}$ - так называемый символ Якоби. Хорошо известно также, что последнее сравнение выполняется не только для простых

, но и для любых целых

, взаимно простых с

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

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

$\begin{displaymath} a^\frac{N-1}{2}\equiv\genfrac{(}{)}{}{0}{a}{N}\pmod N,\quad \text{при } a= -1, 2, 3, \end{displaymath}$ (14)

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

имеем

$\begin{displaymath} b^{\frac{N-1}{2}}\equiv-1\pmod N. \end{displaymath}$

(15)

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

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

$\begin{displaymath} r\equiv1\pmod{24}\text{ или } r\equiv N\pmod{24}. \end{displaymath}$ (16)

Не уменьшая общности, можно считать, что

- простое число. Введем теперь обозначения $N-1=u\cdot 2^k$ , $r-1=v\cdot2^m$ , где

- нечетные числа. Из (15) и сравнения $b^{r-1}\equiv1\pmod r$ следует, что $m\geq k$ . Далее, согласно (14), выполняются следующие сравнения

$\begin{displaymath} \genfrac{(}{)}{}{0}{a}{N}={\genfrac{(}{)}{}{0}{a}{N}}^v\equ... ...genfrac{(}{)}{}{0}{a}{r}}^u\equiv a^{uv2^{m-1}}\!\!\!\pmod r, \end{displaymath}$

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

или

), что

$\begin{displaymath} {\genfrac{(}{)}{}{0}{a}{N}}^{2^{m-k}}=\genfrac{(}{)}{}{0}{a}{r}. \end{displaymath}$

При

это равенство означает, что $\genfrac{(}{)}{}{0}{a}{r}=1$ при

, и, следовательно, $r\equiv1\pmod{24}$ . Если же

, то имеем $\genfrac{(}{)}{}{0}{a}{N}=\genfrac{(}{)}{}{0}{a}{r}$ и $r\equiv N\pmod{24}$ . Этим (16) доказано.

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

Опишем (очень грубо) схему алгоритма Адлемана - Ленстры для проверки простоты :
1) выбираются различные простые числа $p_1,\dots,p_k$ и различные простые нечетные $q_1,\dots, q_s$ такие, что
а) для каждого все простые делители числа содержатся
среди $p_1,\dots,p_k$ и не делятся на квадрат простого числа,
б) $S=2q_1\cdot\ldots\cdot q_s>\sqrt{N}$ ;
2) для каждой пары выбранных чисел , проводятся тесты, подобные сравнению из теоремы 3. Если не удовлетворяет какому-либо из этих тестов - оно составное. В противном случае
3) определяется не очень большое множество чисел, с которыми только и могут быть сравнимы простые делители . А именно, каждый простой делитель числа должен удовлетворять сравнению вида

$\begin{displaymath} r\equiv N^j\pmod S,\quad 0\leq j<T=p_1\cdot\ldots\cdot p_k; \end{displaymath}$

4) проверяется, содержит ли найденное множество делители

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

- простое число.

Если число составное, оно обязательно имеет простой делитель , меньший $\sqrt{N}<S$ , который сам содержится среди возможных остатков. Именно на этом свойстве основано применение пункта 4) алгоритма.

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

$\begin{displaymath}\{p\}=\{2,3,5,7\} \text{ и } \{q\}=\{3,7,11,31,43,71,211\}, \end{displaymath}$

то таким способом удается проверять простоту чисел $N<8{,}5\cdot10^{19}$ .

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

$\begin{displaymath} J(\chi_1,\chi_2)=-\sum\limits_{x=2}^{q-1}\chi_1(x)\chi_2(1-x) \end{displaymath}$

определяется для двух характеров $\chi_1,\chi_2$ по модулю

. Если характеры имеют порядок

, то соответствующая сумма Якоби принадлежит кольцу $\ZZ[\zeta_p]$ . Поскольку числа

, участвующие в алгоритме, сравнительно невелики, то вычисления с суммами Якоби производятся в полях существенно меньшей степени, чем вычисления с суммами Гаусса. Это главная причина, по которой суммы Якоби предпочтительнее для вычислений. При $\chi_1\chi_2\ne\chi_0$ выполняется классическое соотношение

$\begin{displaymath} J(\chi_1,\chi_2)= \frac{\tau(\chi_1)\cdot\tau(\chi_2)}{\tau(\chi_1\cdot\chi_2)}, \end{displaymath}$

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

соответствующее сравнение, справедливое для простых

, отличных от 2, 3, 7, принимает вид

$\begin{displaymath} (-3\zeta-2)^{\raisebox{4pt}{$\scriptstyle\left[\frac{N}{3}\... ...yle\left[\frac{2N}{3}\right]$}} \equiv\xi\pmod{N\ZZ[\zeta]}, \end{displaymath}$

где $\zeta=e^{2\pi i/3}$ и $\xi$ - некоторый корень кубический из 1.

В 1984 г. в работе [15] было внесено существенное усовершенствование в алгоритм, позволившее освободиться от требования неделимости чисел на квадраты простых чисел. В результате, например, выбрав число $T=2^4\cdot3^2\cdot5\cdot7=5040$ и взяв равным произведению простых чисел с условием, что делится на , получим $S>1{,}5\cdot10^{52}$ , что позволяет доказывать простоту чисел , записываемых сотней десятичных знаков. При этом вычисления будут проводиться в полях, порожденных корнями из 1 степеней 16, 9, 5 и 7.

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

Отметим, что оценка сложности этого алгоритма представляет собой трудную задачу аналитической теории чисел. Как уже указывалось, количество операций оценивается величиной $(\ln N)^{c\ln\!\ln\!\ln N}$ . Однако соответствующие числа и , возникающие в процессе доказательства, не могут быть явно указаны в зависимости от . Доказано лишь существование чисел и , для которых достигается оценка. Впрочем, есть вероятностный вариант алгоритма, доказывающий простоту простого числа c вероятностью большей $1-2^{-k}$ за $O(k(\ln N)^{c\ln\!\ln\!\ln N})$ арифметических операций. А в предположении расширенной гипотезы Римана эта оценка сложности может быть получена при эффективно указанных и .