Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.5 Построение больших простых чисел n с использованием частичного разложения n-1 на множители Вверх: 13. Методы построения больших простых чисел Назад: 13.3 Простые числа специального вида   Содержание   Предметный указатель


13.4 Построение больших простых чисел с использованием полного разложения на простые множители

Хорошо известен следующий результат (см., например, обзор [Вас1]).

Теорема 5.  Пусть $ n$ -- нечетное натуральное число, $ n>1$, и $ n-1=\prod\limits_{j=1}^mp_j^{e_j}$ -- известное разложение $ n-1$ на простые множители $ p_j$. Если для каждого $ j=1,\ldots,m$ существует натуральное число $ a_j$ такое, что

$\displaystyle a_j^{n-1}\equiv1\mkern5mu({\rm mod}\,\,n)$   и$\displaystyle \quad a_j^{(n-1)/p_j}\not\equiv1\mkern5mu({\rm mod}\,\,n), $

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

На этой теореме основан следующий метод Миллера построения больших простых чисел. Для некоторого набора известных простых чисел $ p_1=2,p_2,\ldots,p_m$ и показателей $ e_1,\ldots,e_m$ вычисляем $ n=p_1^{e_1}\ldots p_m^{e_m}+1$. С помощью некоторого вероятностного теста (см. раздел 13.2) проверяем, не является ли $ n$ составным. Если нет, т. е. $ n$ вероятно простое, то генерируем случайную последовательность $ a_1,a_2,\ldots$ натуральных чисел из интервала $ (1,n)$. Для каждого $ i$ вычисляем $ a_i^{n-1}\bmod n$ и $ a_i^{(n-1)/p_j}\bmod n$ для всех $ j$ таких, что $ a_l^{(n-1)/p_j}\equiv1\mkern5mu({\rm mod}\,\,n)$ при всех $ l<j$ . Если для некоторого $ i\quad a_i^{n-1}\not\equiv1\mkern5mu({\rm mod}\,\,n)$, то $ n$ составное. В противном случае мы докажем, что $ n$ простое, когда для всех $ j=1,\ldots,m$ найдем $ i=i(j)$ такое, что $ a_{i(j)}^{(n-1)/p_j}\not\equiv1\mkern5mu({\rm mod}\,\,n)$.

В работе Плейстеда [Pl] указан способ правильной организации вычислений для проверки сравнений указанного метода. А именно, следует положить $ d=p_1\ldots p_m$, $ d_1 =p_1\ldots p_{[m/2]}$, $ d_2=p_{[m/2]+1}\ldots p_m$, $ q=(n-1)/d$. Сначала следует вычислить $ a^q\bmod n$, затем $ (a^q)^{d_i}\bmod n$, $ i=1,2$. Наконец, нужно вычислить

$\displaystyle \left(\left(a^q\right)^{d_1}\right)^{d_2/p_j}\bmod n\quad$ для$\displaystyle \quad p_j\mid d_1$    

и


$\displaystyle \left(\left(a^q\right)^{d_2}\right)^{d_1/p_j}\bmod n\quad$ для$\displaystyle \quad p_j\mid d_2,$    

делая это рекурсивно тем же методом. Мы также при этом найдем $ a^{n-1}\bmod n$, возведя в квадрат $ \left(\left(a^q\right)^{d_2}\right)^{d_1/p_1}\bmod n$, так как $ p_1=2$. При вычислениях этим способом требуется $ O(\log n\,\log\log n)$ умножений по модулю $ n$.

Зададимся теперь вопросом: какой из вероятностных тестов и сколько раз применять? Рекомендуется тест Миллера -- Рабина (см. раздел 13.2). Поскольку на отрезке $ [1,n]$ доля простых чисел составляет примерно $ 1/\log n$, то надо применить тест $ k$ раз, где $ k$ определяется из неравенства $ 4^{-k}<1/\log n$. Тогда вероятность того, что $ n$ составное, будет меньше вероятности того, что $ n$ простое (это эвристическое рассуждение).

Подытоживая сказанное, простоту $ n$ такого, что $ n-1=\prod\limits_{j=1}^mp_j^{e_j}$, проверяем с помощью следующего алгоритма.     1. Тестируем $ n$ на простоту методом Миллера -- Рабина $ k$ раз, где $ k$ определяется из неравенства $ 4^{-k}<1/\log n$.

    2. Если не оказалось, что $ n$ составное, то перебираем несколько значений $ a_i$ и для них проверяем условия метода Миллера. Обычно перебирают 4-6 значений $ a_i$.

    3. Если до сих пор не обнаружено, что $ n$ составное и не доказано, что $ n$ простое, то далее чередуют: для одного $ a$ тест Миллера -- Рабина, для трех метод Миллера и т. д. до тех пор, пока не докажут, что $ n$ простое или составное.

Эвристическая оценка сложности проверки простоты чисел $ n$, не превосходящих некоторой границы $ N$, с помощью этого метода составляет $ O\left(\log^2N\right)$ арифметических операций по модулю чисел, не превосходящих $ N$.

Таким образом, для построения больших простых чисел нам остается лишь определить, как выбирать набор $ (p_1,e_1),\ldots,(p_m,e_m)$, т. е. какое взять $ n$. Для этого в [Pl] предложен ряд стратегий.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.5 Построение больших простых чисел n с использованием частичного разложения n-1 на множители Вверх: 13. Методы построения больших простых чисел Назад: 13.3 Простые числа специального вида   Содержание   Предметный указатель

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