10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

78580. Сонце, сонечко та соняшник 51 KB
  Мета: формувати в учнів уявлення про Сонце про залежність життя рослин і тварин від сонячного світла і тепла; розвивати мовленнєві здібності уміння декламувати; виховувати інтерес до знань. Сонце Девіз уроку: Веди нас сонечко в політ Більше дізнаємось про світ.
78581. Почва. Почва – это место, где живут мелкие животные 84 KB
  Цель: продолжить формировать представление о предметах неживой природы, сформировать понятие о почве и её значении в жизни живых существ, познакомить с составом почвы; развивать логическое мышление, внимание, связную речь, навыки исследовательской работы, познавательный интерес...
78582. Різноманітність рослин. Значення рослин у житті людини 87 KB
  Навчати учнів розпізнавати рослини найближчого оточення. Плакат із записом шифрограми; малюнки із зображенням листяних і хвойних дерев; матеріали для ігор; пов’язки із зображенням квітів; дитяча енциклопедія Рослини.
78583. Тварини. Різноманітність тварин 14.53 MB
  Мета: розширити і уточнити знання учнів про різноманітність тварин середовище їхнього існування; про тварин які живуть поряд з людиною; розкрити цінність тварин для людини; розвивати вміння спостерігати за тваринами порівнювати тварин групувати їх; виховувати шанобливе ставлення до тварин.
78584. Сонце в нашому житті 2.33 MB
  Мета уроку: ознайомити учнів із Сонцем як небесною зіркою; розвивати життєві та екологічні компетентності; фантазію уяву кмітливість; виховувати гідне ставлення до природи; Обладнання: підручник робочий зошит кольорові олівці пластилін малюнки таблиці.
78585. Сонце сходить – усе оживає. Сонце заходить усе завмирає 161.5 KB
  Мета. Формувати в учнів уявлення про сонце залежність існування живої природи від сонячного світла і тепла навчити встановлювати зв’язки між живою та не живою природою; виховувати повагу до традицій українського народу вшановувати Сонце.
78586. Комахи в нашому житті 330 KB
  Мета: уточнити уявлення учнів про комах, поширити знання про цих тварин, учити називати істотні ознаки комах, їх будову; розвивати мовленнєві навички, мислення, увагу, спостережливість; виховувати бережливе ставлення до тварин, любов до природи.
78587. Як доглядати за кімнатними рослинами? 52.5 KB
  Мета: формувати уявлення про кімнатні рослини, про залежність від їх потреб в освітленні, поливі, освітленні, пересадці. Розвивати практичні уміння і навички доглядати за кімнатними рослинами (розташування в приміщенні, поливі, розпушуванні ґрунту, пересадка, розмноження).
78588. Осінь. Рослини восени. Як тварини готуються до зими 72.5 KB
  Обладнання: таблиці ілюстрації осінь у парку у лісі на городі осінні листочки костюми Осені білочки їжачка корони місяців овочі та фрукти – дари осені малюнки дітей. Під слова вчителя виходить дівчина Осінь розтрушує листочки Осінь хазяйнує скрізь куди не поглянь.