Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: 4.7. Как раскладывают составные Up: 4. Алгоритмические проблемы теории Previous: 4.5. Как строить большие Contents: Содержание

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

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

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

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

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

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

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

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

\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.   Пусть $ N$ - нечетное простое число, $ (N,pq)=1$. Тогда в кольце $ \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}

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

В случае $ p=2$ легко проверить, что сравнение из теоремы 3 равносильно хорошо известному в элементарной теории чисел сравнению
\begin{displaymath} q^{\frac{N-1}{2}}\equiv\genfrac{(}{)}{}{0}{q}{N}\pmod N, \end{displaymath} (13)

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

Пример 1.   (Х. Ленстра). Пусть $ N$ - натуральное число, $ (N,6)=1$, для которого выполнены сравнения
\begin{displaymath} a^\frac{N-1}{2}\equiv\genfrac{(}{)}{}{0}{a}{N}\pmod N,\quad \text{при } a= -1, 2, 3, \end{displaymath} (14)

а кроме того с некоторым целым числом $ b$ имеем
\begin{displaymath} b^{\frac{N-1}{2}}\equiv-1\pmod N. \end{displaymath} (15)

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

Докажем, что из выполнимости (14-15) следует, что каждый делитель $ r$ числа $ N$ удовлетворяет одному из сравнений
\begin{displaymath} r\equiv1\pmod{24}\text{ или } r\equiv N\pmod{24}. \end{displaymath} (16)

Не уменьшая общности, можно считать, что $ r$ - простое число. Введем теперь обозначения $ N-1=u\cdot 2^k $, $ r-1=v\cdot2^m $, где $ u$ и $ v$ - нечетные числа. Из (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}

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

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

При $ m>k$ это равенство означает, что $ \genfrac{(}{)}{}{0}{a}{r}=1 $ при $ a= -1, 2, 3$, и, следовательно, $ r\equiv1\pmod{24} $. Если же $ m=k$, то имеем $ \genfrac{(}{)}{}{0}{a}{N}=\genfrac{(}{)}{}{0}{a}{r} $ и $ r\equiv N\pmod{24} $. Этим (16) доказано.

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

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

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

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

Если число $ N$ составное, оно обязательно имеет простой делитель $ r$, меньший $ \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$ по модулю $ q$. Если характеры имеют порядок $ p$, то соответствующая сумма Якоби принадлежит кольцу $ \ZZ[\zeta_p] $. Поскольку числа $ 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]). Так, при $ p=3$ и $ q=7$ соответствующее сравнение, справедливое для простых $ N$, отличных от 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] было внесено существенное усовершенствование в алгоритм, позволившее освободиться от требования неделимости чисел $ q-1$ на квадраты простых чисел. В результате, например, выбрав число $ T=2^4\cdot3^2\cdot5\cdot7=5040 $ и взяв $ S$ равным произведению простых чисел $ q$ с условием, что $ T$ делится на $ q-1$, получим $ S>1{,}5\cdot10^{52} $, что позволяет доказывать простоту чисел $ N$, записываемых сотней десятичных знаков. При этом вычисления будут проводиться в полях, порожденных корнями из 1 степеней 16, 9, 5 и 7.

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

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

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

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100