10047

Тест Рабина-Миллера проверки чисел на простоту

Доклад

Информатика, кибернетика и программирование

Тест Рабина-Миллера проверки чисел на простоту. При тестировании чисел на простоту с помощью вероятностного теста основанного на малой теореме Ферма может возникнуть ситуация когда вероятность ошибки не снижается с количеством повторений теста. В этом случае она...

Русский

2013-03-20

57 KB

41 чел.

Тест Рабина-Миллера проверки чисел на простоту.

При тестировании чисел на простоту с помощью вероятностного теста, основанного на малой теореме Ферма, может возникнуть ситуация, когда вероятность ошибки не снижается с количеством повторений теста.

В этом случае она равна единице и в результате тестирования может быть принято неверное решение. В этой связи разработаны и применяются на практике вероятностные тесты, свободные от указанного недостатка, например, тест Соловея-Штрассена. При повторении теста Соловея-Штрассена раз, вероятность неотбраковки составного числа . Существенно более эффективным вероятностным тестом является тест Рабина-Миллера.

В тесте Рабина-Миллера используется критерий, основанный на факте, что для простого модуля квадратными корнями из единицы являются лишь числа , а для составного нечетного модуля   , , число таких корней больше двух.

Пусть - нечетное натуральное число. Тогда можно записать , где - нечетное и .  Если число - простое, то , при . Поэтому квадратные корни из единицы имеют вид:, где показатель равен .

При извлечении квадратных корней из единицы по простому модулю мы либо все время будем получать единицу, либо возникнет корень равный .

Это означает, что в ряду вычетов чисел , , по простому модулю либо появится , либо все они сравнимы с единицей, что возможно, когда .

Если - составное, то возможны и другие случаи.

Основанный на данном замечании тест Рабина-Миллера заключается в следующем:

1) псевдослучайно выбираем вычет , проверяем условие . Если условие не выполнено, значит, - составное и работа закончена;

2) вычисляем . Если , то не исключено, что число - простое и необходимо перейти на начало, чтобы  повторить тест для другого основания;

3) вычисляем последовательно вычеты чисел , по модулю , пока не появится –1, либо не исчерпается список;

4) если –1 обнаружена в списке, то не исключено, что число - простое и необходимо перейти на начало, чтобы  повторить тест для другого основания;

5) если ни одно число из списка не сравнимо с –1, то число - составное и необходимо закончить работу.

Назовем составное число , где , - нечетно, сильно псевдопростым по основанию , если выполняется одно из двух условий: , либо в последовательности , существует число, сравнимое с –1 по модулю .

Известно, что такие составные числа, которые при соответствующих проходят тест Рабина-Миллера, существуют.

Однако можно показать, что при повторении теста Рабина-Миллера раз, вероятность неотбраковки составного числа .


 

А также другие работы, которые могут Вас заинтересовать

78683. КОРПОРАТИВНАЯ ОТЧЁТНОСТЬ В УСЛОВИЯХ СОВРЕМЕННОЙ МОДЕРНИЗАЦИИ 1.63 MB
  Традиционный способ подготовки отчетности, а также содержание отчетности за последнее время стало подвергаться общественному недоверию в связи с рядом банкротств и финансовых скандалов. Это отрицательным образом сказалось на всех участниках, задействованных в рыночных отношениях.
78684. Комплексний історико-правовий аналіз інституту адвокатури в Україні 898 KB
  Інститут адвокатури у такому вигляді, як він існує в наш час, володіє рядом властивостей, які ми вважаємо самі по собі зрозумілими. Проте визнання суспільством ролі адвокатури як єдиного незалежного професійного правозахисного інституту, покликаного захищати права та свободи...
78685. НЕПОСРЕДСТВЕННЫЕ РЕЗУЛЬТАТЫ СОЧЕТАННЫХ ОПЕРАЦИЙ ТРАНСМИОКАРДИАЛЬНОЙ ЛАЗЕРНОЙ РЕВАСКУЛЯРИЗАЦИИ И АОРТОКОРОНАРНОГО ШУНТИРОВАНИЯ У БОЛЬНЫХ ИБС 4.98 MB
  Они изучали теоретическую возможность поступления крови в миокард прямо из полости левого желудочка по специально созданным каналам. За основу принималась модель перфузии миокарда у рептилий, у которых система коронарных артерий отсутствует, а кровь доставляется из полости сердца в синусоиды.
78686. КАТАМНЕЗ ЛИЦ, УВОЛЕННЫХ ИЗ ВООРУЖЕННЫХ СИЛ С ПОГРАНИЧНЫМИ ПСИХИЧЕСКИМИ РАССТРОЙСТВАМИ 6.55 MB
  Для достижения цели были сформулированы следующие задачи: Изучить зависимость показателей катамнеза от клиники психических расстройств инициального периода болезни. Проанализировать динамику психического состояния и качество социальной адаптации военнослужащих с разной выраженностью...
78687. УПРАВЛЕНИЕ ПРОИЗВОДСТВЕННЫМ РАЗВИТИЕМ ТЕКСТИЛЬНЫХ ПРЕДПРИЯТИЙ 3.33 MB
  Необходимость шагов инновационного развития экономики России, направленных, в частности, на решение проблем восстановления производственного потенциала и дальнейшего развития конкурентоспособности различных народнохозяйственных комплексов и, в первую очередь, промышленности...
78688. Управление рисками инвестиционных проектов в пищевой промышленности 2.75 MB
  В третьей главе диссертации Методические аспекты управления рисками инвестиционных проектов в пищевой промышленности выявлены методы защиты от рисков; разработаны механизмы оптимизации защитных мероприятий реализуемых при...
78689. Роль инновационных социотехнических систем в переходе к устойчивому развитию (философские аспекты) 2.79 MB
  Современное общество, подобно современному программному обеспечению, характеризуется как общество, структуры которого подвергаются постоянному обновлению. Находясь в подвижном состоянии, общество обновляет и трансформирует все свои системы, постоянно приближаясь к наиболее комфортному состоянию.
78690. Восстановление и развитие школьной системы в Нижнем Поволжье в 1945–1953 годов 2.6 MB
  Исследование проблемы восстановления и развития школьной системы в 1945–1953 гг. представляется возможным на примере одного из типичных регионов страны – Нижнего Поволжья. Масштабы разрушений и механизм их преодоления, сложившиеся в регионе, являлись типичными для всего Советского Союза...
78691. Воспитание гуманистического отношения к природе у учащихся в процессе изучения естественнонаучных дисциплин 943 KB
  Объект исследования: процесс воспитания гуманистического отношения к природе у учащихся средней и старшей ступеней общеобразовательной школы в ходе освоения ими содержания естественнонаучных дисциплин. Предмет исследования: педагогические средства, условия, факторы успешности процесса воспитания...