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


4.4. Как отличить составное число от простого

Существует довольно эффективный способ убедиться, что заданное число является составным, не разлагая это число на множители. Согласно малой теореме Ферма, если число $ N$ простое, то для любого целого $ a$, не делящегося на $ N$, выполняется сравнение
\begin{displaymath} a^{N-1}\equiv1\pmod N. \end{displaymath} (9)

Если же при каком-то $ a$ это сравнение нарушается, можно утверждать, что $ N$ - составное. Проверка (9) не требует больших вычислений, это следует из алгоритма 1. Вопрос только в том, как найти для составного $ N$ целое число $ a$, не удовлетворяющее (9). Можно, например, пытаться найти необходимое число $ a$, испытывая все целые числа подряд, начиная с 2. Или попробовать выбирать эти числа случайным образом на отрезке $ 1<a<N$.

К сожалению, такой подход не всегда дает то, что хотелось бы. Имеются составные числа $ N$, обладающие свойством (9) для любого целого $ a$ с условием $ (a,N)=1$. Такие числа называются числами Кармайкла. Рассмотрим, например, число $ 561=3\cdot11\cdot17$. Так как $ 560$ делится на каждое из чисел $ 2$, $ 10$, $ 16$, то с помощью малой теоремы Ферма легко проверить, что $ 561$ есть число Кармайкла. Можно доказать (Carmichael, 1912), что любое из чисел Кармайкла имеет вид $ N=p_1\cdot\ldots\cdot p_r $, $ r\geq3 $, где все простые $ p_i $ различны, причем $ N-1$ делится на каждую разность $ p_i-1 $. Лишь недавно, см. [10], была решена проблема о бесконечности множества таких чисел.

В 1976 г. Миллер предложил заменить проверку (9) проверкой несколько иного условия. Детали последующего изложения можно найти в [8]. Если $ N$ - простое число, $ N-1=2^s\cdot t $, где $ t$ нечетно, то согласно малой теореме Ферма для каждого $ a$ с условием $ (a,N)=1$ хотя бы одна из скобок в произведении

\begin{displaymath} (a^t-1)(a^t+1)(a^{2t}+1)\cdot\ldots\cdot(a^{2^{s-1}t}+1)= a^{N-1}-1 \end{displaymath}

делится на $ N$. Обращение этого свойства можно использовать, чтобы отличать составные числа от простых.

Пусть $ N$ - нечетное составное число, $ N-1=2^s\cdot t $, где $ t$ нечетно. Назовем целое число $ a$, $ 1<a<N$, ``хорошим'' для $ N$, если нарушается одно из двух условий:
$ \alpha$) $ N$ не делится на $ a$;
$ \beta$) $ a^t\equiv1\pmod N $ или существует целое $ k$, $ 0\leq k<s $, такое, что

\begin{displaymath} a^{2^kt}\equiv-1\pmod N. \end{displaymath}

Из сказанного ранее следует, что для простого числа $ N$ не существует хороших чисел $ a$. Если же $ N$ составное число, то, как доказал Рабин, их существует не менее $ \frac{3}{4}(N-1)$.

Теперь можно построить вероятностный алгоритм, отличающий составные числа от простых.


5. Алгоритм, доказывающий непростоту числа

  • Выберем случайным образом число $ a$, $ 1<a<N$, и проверим для этого числа указанные выше свойства $ \alpha)$ и $ \beta)$.
  • Если хотя бы одно из них нарушается, то число $ N$ составное.
  • Если выполнены оба условия $ \alpha)$ и $ \beta)$, возвращаемся к шагу 1.


    • Из сказанного выше следует, что составное число не будет определено как составное после однократного выполнения шагов 1-3 с вероятностью не большей $ 4^{-1} $. А вероятность не определить его после $ k$ повторений не превосходит $ 4^{-k} $, т.е. убывает очень быстро.

    Миллер предложил детерминированный алгоритм определения составных чисел, имеющий сложность $ O(\ln^3 N)$, однако справедливость его результата зависит от недоказанной в настоящее время расширенной гипотезы Римана. Согласно этому алгоритму достаточно проверить условия $ \alpha$) и $ \beta$) для всех целых чисел $ a, 2\leq a\leq70\ln^2N$. Если при каком-нибудь $ a$ из указанного промежутка нарушается одно из условий $ \alpha$) или $ \beta$), число $ N$ составное. В противном случае оно будет простым или степенью простого числа. Последняя возможность, конечно, легко проверяется.

    Напомним некоторые понятия, см. [4], необходимые для формулировки расширенной гипотезы Римана. Они понадобятся нам и в дальнейшем. Пусть $ m\geq2 $ - целое число. Функция $ \chi:\ZZ\to\CC $ называется характером Дирихле по модулю $ m$, или просто характером, если эта функция периодична с периодом $ m$, отлична от нуля только на числах, взаимно простых с $ m$, и мультипликативна, т.е. для любых целых $ u,v$ выполняется равенство $ \chi(uv)=\chi(u)\chi(v) $. Для каждого $ m$ существует ровно $ \phi(m)$ характеров Дирихле. Они образуют группу по умножению. Единичным элементом этой группы является так называемый главный характер $ \chi_0 $, равный 1 на всех числах, взаимно простых с $ m$, и 0 на остальных целых числах. Порядком характера называется его порядок как элемента мультипликативной группы характеров.

    С каждым характером связана так называемая $ L$-функция Дирихле - функция комплексного переменного $ s$, определенная рядом $ \ds L(s,\chi)=\sum\limits_{n=1}^{\infty}\frac{\chi(n)}{n^s}$. Сумма этого ряда аналитична в области $ \Re s>1 $ и может быть аналитически продолжена на всю комплексную плоскость. Следующее соотношение $ \ds L(s,\chi_0)=\zeta(s)\prod\limits_{p\vert m}(1-p^{-s}) $ связывает $ L$-функцию, отвечающую главному характеру, с дзета-функцией Римана $ \ds\zeta(s)=\sum\limits_{n=0}^{\infty}\frac{1}{n^s} $. Расширенная гипотеза Римана утверждает, что комплексные нули всех $ L$-функций Дирихле, расположенные в полосе $ 0<\Re s<1 $, лежат на прямой $ \Re s\!=\!\nfrac{1}{2}$. В настоящее время не доказана даже простейшая форма этой гипотезы - классическая гипотеза Римана, утверждающая такой же факт о нулях дзета-функции.

    В 1952 г. Анкени с помощью расширенной гипотезы Римана доказал, что для каждого простого числа $ q$ существует квадратичный невычет $ a$, удовлетворяющий неравенствам $ 2\leq a\leq70\ln^2q $. Константа $ 70$ была сосчитана позднее. Именно это утверждение и лежит в основе алгоритма Миллера. В 1957 г. Берджесс доказал существование такого невычета без использования расширенной гипотезы Римана, но с худшей оценкой $ 2\leq a\leq q^{\frac{1}{4\sqrt{e}}}+\varepsilon $, справедливой при любом положительном $ \varepsilon $ и $ q$, большем некоторой границы, зависящей от $ \varepsilon $.

    Алгоритм Миллера принципиально отличается от алгоритма 5, так как полученное с его помощью утверждение о том, что число $ N$ - составное, опирается на недоказанную расширенную гипотезу Римана и потому может быть неверным. В то время как вероятностный алгоритм 5 дает совершенно правильный ответ для составных чисел. Несмотря на отсутствие оценок сложности, на практике он работает вполне удовлетворительно.

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

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