|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Miroshnichenko 2:5020/400 11 Oct 2001 15:28:51
To : Evgeny Zhykh
Subject : Re: простые числа
--------------------------------------------------------------------------------
Лучше всего запрограммировтаь тест на простоту Рабина-Миллера.
Вот описалово:
====
Тест является вероятностным. Это означает, что он использует датчик
случайных чисел и, таким образом, работает не детерминировано. Для входного
целого числа n тест Рабина может выдать один из следующих двух ответов.
1. Число n является составным.
2. Hе знаю.
В случае первого ответа число n действительно является составным, тест
Рабина предъявляет доказательство этого факта. Второй ответ может быть выдан
как для простого, так и для составного числа n. Однако для любого составного
числа n вероятность второго ответа не превышает 1/4. Ценность теста Рабина
состоит именно в неравенстве, ограничивающем сверху вероятность второго
ответа для произвольного составного числа n. Таким образом, если мы применим
100 раз тест Рабина к числу n и получим 100 ответов "не знаю", то можно с
большой вероятностью утверждать, что число n простое. Более точно,
вероятность получения ста ответов "не знаю" для составного числа n не
превышает 4-100, т.е. практически равна нулю. Тем не менее тест Рабина не
предъявляет доказательства того, что число n простое.
Перейдем непосредственно к изложению теста Рабина . Мы проверяем простоту
входного числа n. Допустим сразу, что число n нечетное. (Существует только
одно четное простое число -- 2.) Тогда число n - 1 четное. Представим его в
виде (2.1):
n - 1 = (2^t) * s
(2.1)
где s -- нечетное число. Выберем случайное число b такое, что b !?{0,1}(mod
n), где b выбирается случайно.
Используя алгоритм быстрого возведения в степень по модулю n, вычислим
следующую последовательность (2.2) элементов кольца Zn:
Х0 = b^s (mod n),
Х1 = Х0 * Х0 (mod n), (2.2)
...
Хt = Хt-1 * Хt-1 (mod n) = b(n-1) (mod n)
Тест Рабина выдает ответ "n -- составное число" в случае, если
1) Хt !? 1 (mod n), или
2) в последовательности Х0, Х1, Х2 : Хt имеется фрагмент вида ..., *, 1,
...
где звездочкой обозначено число, отличное от единицы или минус единицы по
модулю n. В противном случае тест Рабина выдает ответ "не знаю".
Последовательность Х0, Х1, Х2 : Хt в этом "плохом" случае либо начинается с
единицы, либо содержит (-1) где-нибудь не в конце.
--
Отправлено через сервер Talk.Ru - http://www.talk.ru
--- ifmail v.2.15dev5
* Origin: Talk.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: простые числа 
