10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

24285. PR в организациях социальной сферы 40.5 KB
  Сфера культуры сфера преимущественно некоммерческой деятельности. Панкрухин В принятии решения о спонсорской поддержке организаций культуры ведущее место занимают следующие аргументы: увеличение узнаваемости имени усиление образа компании брендинг; возможности доступа к целевым аудиториям реализация продукции маркетинг; развитие отношений с клиентами и партнерами; социальная ответственность социальное инвестирование развитие связей с сообществом и улучшение качества жизни в местах присутствия компании; возможность улучшения...
24287. PR в финансовой сфере 72.5 KB
  ОСНОВНЫЕ НАПРАВЛЕНИЯ PR ДЕЯТЕЛЬНОСТИ В БАНКАХ. СОЗДАНИЕ ИМИДЖА БАНКА. Благополучие банков перспективы роста базируются не только на эффективных технологиях и необходимых связях но в большей степени на репутации и имидже банка. Создание имиджа можно до определенной степени форсировать а складывание репутации никогда не может обогнать естественного хода развития самого банка его финансовой интеллектуальной и организационной мощи.
24290. Состояние и перспективы развития рынка PR-услуг в России 46.5 KB
  Российский рынок PRуслуг формировался весьма активно. Только с развитием демократии становлением рыночных отношений и появлением соответствующих потребностей в области экономики и политики сфера PRуслуг стала быстро развиваться. PRагентства существенно расширяют перечень оказываемых услуг предлагая разработку концепции общественно полезной значимости предприятия создание имиджа товаров соответствующий тренинг высшего руководства подготовку взаимодействия со СМИ исследование социальнопсихологич.
24291. Особенности и основные этапы развития журналистики в ХХ веке 54.5 KB
  С гласностью стали возникать политические партии из подполья вышли социалдемократические эсеровские газеты были созданы вновь газеты и журналы партий народных социалистов народной свободы 17 октября трудовиков промышленников кадетов и т. Это были новые типы изданий: газетыманифесты газетыпризывы дискуссионные листки. В стране действовала Конституция работал парламент права цензуры ограничивались законом Оппозиционные правительству партии имели право на издание легальных газет: большевистская фракция РСДРП в Госдуме издавала...
24292. СМК, их характеристика и роль в деятельности PR-структур 38 KB
  Современная система СМК делится на три вида информационных каналов: СМИ телекоммуникацию и информатику. К СМИ относятся: организационнотехнические комплексы позволяющие осуществлять скорую передачу массовое тиражирование больших объемов словесной образной и музыкальной информации. В структуру системы СМИ входят: 1 газеты журналы дайджесты еженедельники и др. Очень часто термины средства массовой коммуникации СМК и средства массовой информации СМИ употребляются как синонимы.