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


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

Справедлива следующая теорема [BriLS]:

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

$\displaystyle a_j^{n-1}\equiv1\mkern5mu({\rm mod}\,\,n),$   и$\displaystyle \quad\left(a_j^{(n-1)/q_j} -1,n\right)=1, $

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

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

Будем индуктивно строить возрастающую последовательность простых чисел $ p_1<p_2<p_3<\ldots$ до тех пор, пока не построим число нужной величины. В качестве $ p_1$ можно взять любое известное простое число. Предположим, что $ p_{i-1}$ уже построено. Случайным образом выберем натуральное число $ r$ из промежутка $ 1\leqslant r\leqslant p_{i-1}-1$. Пусть $ r=2^st$, где $ t$ нечетно. Положим $ n=2^{s+1}p_{i-1}t+1$. Тогда $ n-1=FR$, где $ F=2^{s+1}p_{i-1}$, $ R=t$; так как $ n<2^{s+2} p_{i-1}t<2^{s+2}p^2_{i-1}\leqslant F^2$, имеем $ F>\sqrt n$. Переберем несколько значений $ a_j$, $ j=1,2$, и проверим для них условия теоремы 6 (здесь $ m=2$, $ q_1=2$, $ q_2=p_{i-1}$). Если эти условия выполнены, то мы полагаем $ p_i=n$. В противном случае следует выбрать другое значение $ r$.

Замечание.  Построив $ n=2^{s+1}p_{i-1}t+1$, уместно применить к нему вероятностный метод Миллера -- Рабина (см. раздел 13.2); если окажется, что $ n$ составное, то следует сразу перейти к выбору нового $ r$.

Можно изменить процедуру построения $ p_i$ по $ p_{i-1}$ в вышеописанном алгоритме следующим образом. Если $ p_{i-1}>3$, то случайно выбираем четное число $ r$ такое, что $ 1\leqslant r\leqslant p_{i-1}-3$. Положим $ n=p_{i-1}r+1$. Тогда $ n-1=FR$, где $ F=p_{i-1}$, $ R=r$; кроме того, выполнено неравенство $ p_{i-1}>\sqrt n$, так как если $ p_{i-1}\leqslant\sqrt n$, то $ n=p_{i-1}r+1\leqslant p_{i-1}(p_{i-1}-3)+1=p_{i-1}^2-3p_{i-1}+1\leqslant n-3\cdot 5+1<n$, и мы пришли к противоречию. Поэтому согласно теореме 6 для доказательства простоты $ n$ достаточно найти одно натуральное число $ a$ такое, что

$\displaystyle a^{n-1}\equiv1\mkern5mu({\rm mod}\,\,n)$   и$\displaystyle \quad(a^{(n-1)/p_{i-1}}-1,n)=1. $

Если такое $ a$ найдено, то мы полагаем $ p_i=n$. В противном случае следует выбрать другое значение $ r$.

Возможно дальнейшее уменьшение нижней границы для $ F$ в теореме 6, например, до $ (n/2)^{1/3}$ (см. [BriLS]). Это приводит к дальнейшему усовершенствованию указанного метода построения больших простых чисел (см. [CQ]).

Существуют также методы (аналогичные описанным в разделах 13.4 и 13.5) построения больших простых чисел $ n$ с помощью полного или частичного разложения $ n+1$ на множители (см. [BaWag]).

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

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