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


13.3 Простые числа специального вида

Здесь мы приведем ряд тестов для доказательства простоты чисел специального вида.

Следующая теорема дает эффективно проверяемый критерий простоты чисел вида $ n=2^m-1$.

Теорема 2 [Кнут, $ \mathsection$ 4.5.4]. Пусть $ m$ -- нечетное натуральное число, а $ n=2^m-1$. Определим последовательность $ \{L_t\}$ по формуле

$\displaystyle L_0=4,\ L_{t+1}=(L^2_t-2)\bmod n,\quad t=0,1,\ldots.
$

Тогда число $ n$ простое тогда и только тогда, когда $ L_{m-2}=0$.

Отметим, что числа вида $ 2^m-1$ могут быть простыми только при простом $ m$, так как если $ d\mid m$, то $ 2^d-1\mid
2^m-1$. Поэтому теорема 2 полезна только для проверки простоты чисел вида $ 2^p-1$, где $ p$ -- простое число, т. е. для нахождения чисел Мерсенна (простых чисел вида $ 2^p-1$). Их в настоящее время известно немногим более 30.

В работе [Will] предложены специальные тесты для проверки простоты чисел вида $ k2^l3^m-1$. Изучение этих чисел продолжено в недавней работе [Gut]. В работе [Wil2] специальные тесты предлагаются для чисел вида $ a5^n-1$ и $ a7^n-1$, а в работе [Wil3] -- для чисел вида $ 6^{2^n}+1$ и $ 10^{2^n}+1$. В работе [BuCP] изучаются простые числа вида $ n!\pm1$ и $ 2\cdot 3\cdot
5\cdot\ldots p\pm1$. См. также работу [WilS], в которой изучаются тесты простоты для чисел специального вида.

Имеются тесты, позволяющие строить пары простых чисел специального вида.

Теорема 3 [Чеб].  Если $ p$ и $ q$ -- простые числа, причем $ p=2q+1$, то     1) при $ q\equiv1\mkern5mu({\rm mod}\,\,4)$ $ g=2$ является первообразным корнем по модулю $ p$;

    2) при $ q\equiv3\mkern5mu({\rm mod}\,\,4)$ $ g=-2$ является первообразным корнем по модулю $ p$.

Таким образом, если $ q$ -- простое число, то для проверки простоты $ p=2q+1$ достаточно проверить выполнение сравнений

$\displaystyle a^{p-1}\equiv1\mkern5mu({\rm mod}\,\,p),\quad a^2\not\equiv1\mkern5mu({\rm mod}\,\,p),\quad a^q\not\equiv1\mkern5mu({\rm mod}\,\,p)
$

для $ a=2$ или $ a=-2$ (при $ q\equiv1\mkern5mu({\rm mod}\,\,4)$ или $ q\equiv3\mkern5mu({\rm mod}\,\,4)$ соответственно).

Работы [CP], [PSZ] посвящены построению близнецов, т. е. пар простых чисел $ p$ и $ p+2$.

Заметим, что в данном разделе мы проверяли на простоту числа $ n$, для которых известно разложение $ n-1$ или $ n+1$ на простые множители. Общие методы построения больших простых чисел, к описанию которых мы перейдем далее, также существенно используют известное разложение $ n\pm 1$ на множители.

Интересный метод построения больших простых чисел специального вида предложен Пинцем, Стейгером и Семереди в [PSS]. Справедлива следующая теорема.

Теорема 4.  Пусть $ n$ -- натуральное число вида $ n=c9^m+d3^m+1$, где $ 1\leqslant c<3^m$, $ 1\leqslant
d\leqslant3^m$. Тогда для простоты $ n$ необходимо и достаточно выполнения следующих двух условий:     1) $ d^2-4c$ не является квадратом целого неотрицательного числа;

    2) существует натуральное число $ l$ такое, что

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

Из этой теоремы следует такой способ построения больших простых чисел.     1. Выбрать $ m,c,d$, где $ 1\leqslant c<3^m$, $ 1\leqslant
d\leqslant3^m$, и положить $ n=c9^m+d3^m+1$.

    2. Проверить условие 1) теоремы 4; если оно не выполнено, то $ n$ составное.

    3. Для всех натуральных $ l$ таких, что $ 1<l\leqslant\lambda\log n$, проверять условие 2) теоремы 4 ($ \lambda$ -- некоторая постоянная). Из невыполнения этого условия может следовать, что $ n$ составное. Если же при некотором $ l$ условие 2) выполнено, то $ n$ -- простое число.

Оценка сложности алгоритма -- $ O(\log n)$ арифметических операций.

Важной отличительной чертой предложенного метода является то, что при некотором значении $ \lambda$ существует бесконечно много простых чисел $ n=c9^m+d3^m+1$, простота которых действительно устанавливается данным алгоритмом. При этом количество таких $ n$, $ n\leqslant x$, оценивается снизу величиной $ \lambda_1x^{2/3}/\log x$, где $ \lambda_1$ -- также абсолютная постоянная.

В работе Гордона [Gor] обсуждается вопрос о построении "сильных" простых чисел $ p$, для которых $ p-1=ar$, $ p+1=bs$, $ r-1=ct$, где $ r$, $ s$, $ t$ -- достаточно большие простые числа. Такие $ p$ важны, например, для криптосистемы RSA. Доказано следующее утверждение: если $ r$, $ s$ -- различные нечетные простые числа, $ p$ -- нечетное простое число, то $ p\equiv1\mkern5mu({\rm mod}\,\,2r)$ и $ p\equiv-1\mkern5mu({\rm mod}\,\,2s)$ тогда и только тогда, когда $ p=p_0+2krs$, где $ p\equiv s^{r-1}-r^{s-1}\mkern5mu({\rm mod}\,\,rs)$ и $ p_0$ нечетно. Поэтому если $ t$, $ r$, $ s$ уже построены, то $ p$ следует искать в прогрессии $ p_0+2rsk$, где $ k$ пробегает множество натуральных чисел. Однако автор предлагает проверять простоту $ p$ вероятностным способом. Здесь можно предложить использовать методы, описываемые ниже, поскольку известно частичное разложение $ p\pm1$ на множители.


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


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