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


13.2 Вероятностные тесты на простоту

Далее мы будем находить большие простые числа, перебирая натуральные числа из некоторых множеств. Нам необходимо быстро обнаруживать и отбрасывать числа, являющиеся составными, и оставлять для дальнейшего строгого доказательства простоты числа, которые скорее всего (с высокой вероятностью) действительно будут простыми. Этой цели служат вероятностные тесты на простоту. Такие тесты либо определяют, что $ n$ составное, либо не дают определенного ответа о простоте $ n$. Однако во втором случае $ n$ будет простым с высокой вероятностью. Вероятностные тесты быстро отсеивают составные числа, однако доказать с их помощью простоту числа нельзя.

Рассмотрим алгоритм Миллера -- Рабина [Rab]. Именно он обычно используется при построении больших простых чисел. Алгоритм основан на следующей теореме.

Теорема 1.  Пусть $ n$ -- нечетное составное число. Рассмотрим множество $ W(n)$ натуральных чисел $ b$, $ 1<b<n$, для которых выполнено одно из следующих условий:     1) $ b^{n-1}\not\equiv1\mkern5mu({\rm mod}\,\,n)$;

    2) при некотором $ i$ таком, что $ 2^i\mid n-1$, выполнены неравенства

$\displaystyle 1<\left(b^{(n-1)/2^i} -1,n\right)<n.
$

Тогда количество элементов в $ W(n)$ не меньше $ 3(n-1)/4$.

Алгоритм Миллера -- Рабина заключается в случайном переборе значений $ b$, $ 1<b<n$, и проверке для них условий 1) и 2). Если хотя бы одно из них выполнено, то $ n$ -- составное число. Если же эти условия не выполнены для $ k$ случайных значений $ b_1,\ldots,b_k$, то можно считать, что $ n$ -- простое с вероятностью не менее $ 1-4^{-k}$.

Имеются и другие работы, посвященные вероятностным тестам на простоту (см. [SStr], [BBCGP], [Mon], [Boyd1], [DiPFM], [AS], [JU]). Однако для практических целей тест Миллера -- Рабина вполне эффективен и достаточен.

В работе [BBCGP] обсуждается вопрос, насколько соответствует действительности утверждение "вероятно простое" для числа $ n$, успешно прошедшего тест Миллера -- Рабина $ k$ раз? Ответ таков: мы верим, что $ n$ простое, поскольку иначе мы наблюдали чрезвычайно редкое событие вероятности не более $ 4^{-k}$. Однако здесь возникает другой вопрос о случайности выбираемых в тесте значений $ b$ и о том, как распределены на отрезке $ [2,n-1]$ натурального ряда те числа $ b$, для которых тест не выполняется (в случае составного $ n$).


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


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

TopList Rambler's Top100