Тест на простоту Миллера-Рабина
Теперь, наконец, мы располагаем достаточной информацией для того, чтобы привести тест Миллера-Рабина. Этот тест, как и тесты Ферма и Соловея-Штрассена, строит вероятно простые числа, то есть число, опознанное этим тестом как простое, может с некоторой малой вероятностью оказаться составным, однако вероятность ошибки у теста Миллера-Рабина гораздо ниже, чем у первых двух тестов. Как правило, для опознания простого числа достаточно одной итерации теста, но все же рекомендуемое количество итераций – пять. Тест Миллера-Рабина основан на двух важных фактах: 1) Согласно теореме Ферма, если n – простое число, то для любого a: 0<a<n выполняется an—1≡1(mod n); 2) Если n – простое число, то сравнение x2≡1(mod n) имеет только тривиальные корни x≡±1(mod n), а если n – составное, то такое сравнение имеет несколько корней помимо тривиальных. Тест Миллера-Рабина: Вход: n=2sr+1 – нечетное число, проверяемое на простоту, s≥0, r – нечетное. t - количество итераций, параметр надежности. 1. Повторить t раз следующие шаги: 1.1. Случайным образом выбрать a: 1<a<n—1. 1.2. Строим последовательность b0, b1,…,bs, где bj= mod n, j=0,1,…,s. 1.3. Если в построенной последовательности не встретилась «1», то идти на Выход с сообщением «n - составное число». 1.4. Если перед первой единицей в последовательности стоит не «-1», то идти на Выход с сообщением «n - составное число». 2. Идти на Выход с сообщением «n – простое число с вероятностью εt». Выход. Обратим внимание на то, что в последовательности b0, b1,…,bs каждый последующий член является квадратом предыдущего по модулю n, а последний член есть ни что иное как an—1 mod n. Вероятность ошибки ε ≤ φ(n)/4n, то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма. Пример 1. n=65=64+1=26+1. r=1, s=6. t=5. 1. 1-я итерация: 1.1. a=8. 1.2. Составляем последовательность: 8, 64=—1, 1, 1, 1, 1. 1.3. В последовательности встретилась «1». 1.4. Перед первой единицей стоит —1. 1. 2-я итерация: 1.1. a=11. 1.2. Составляем последовательность: 11, 56, 16, 61, 16, 61. 1.3. В последовательности не встретилась «1». Выход: « n - составное число».
В том случае, когда тест Миллера-Рабина определяет составность числа n на шаге 1.4, появляется возможность частично факторизовать n. Действительно, пусть в последовательности b0, b1,…,bs, где bj= mod n, нашлось такое i, что bi≠±1, bi+1=1. Обозначим для краткости bi=b. Тогда bi+1=b2≡1(mod n). Тогда n\(b2—1) n\(b+1)(b—1). Но в силу того, что b ±1(mod n), n не делит (b+1), n не делит (b—1). Следовательно, 1<НОД(n, b—1)<n,1<НОД(n, b+1)<n. Значит, НОД(n,b—1) и НОД(n,b+1) являются нетривиальными делителями числа n. Пример 2 n=161=160+1=25·5+1. r=5, s=5. 1. 1-я итерация: 1.1. a=22. a5 mod 161 = 225 mod 161=22. 1.2. Составляем последовательность: 22, 1, 1, 1, 1, 1. 1.3. В последовательности встретилась «1». 1.4. Перед первой единицей стоит 22. Выход: « n - составное число». Факторизуем 161: b=22. b+1=23, b—1=21. Вычислим НОД(161, 23): 161=23·7+0. НОД(161,21): 161=21·7+14 21=14·1+7 14=7·2+0. Итак, нашли два нетривиальных делителя 161, и получили 161=23·7. Надо заметить, что на самом деле случай, когда в тесте Миллера-Рабина возникает возможность факторизации, происходит весьма редко. Гораздо чаще сообщение о составности мы получаем на шаге 1.3.
Популярное: Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (2148)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |