10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

14257. Принципы использования музыки в звуковом кино 14.18 KB
  Принципы использования музыки в звуковом кино. Музыка в фильме не нуждается ни в тематической интеграции ни в стилистическом единстве; если это требуется сценарием рядом могут стоять вокальная музыка разных народов джаз концертная музыка и т. д. Для киномузыки необяз...
14258. Сложные формы в музыке 14.52 KB
  Сложные формы 1. сонатная форма сонатное allegro музыкальная форма основанная на сопоставлении и развитии 2х тем обычно контрастных. Представляет обширные возможности для воплощения драматизма в музыке. Применяется преимущественно в инструментальных произведениях. ...
14259. Простые формы в музыке 13.43 KB
  Простые формы ПРОСТЫЕ ФОРМЫ муз. формы из 2 или 3 частей возможны повторения каждая из которых не сложнее периода. Проста́я двухча́стная фо́рма музыкальная форма состоящая из двух частей первая из которых является периодом а вторая не содержит форм более сложных...
14260. Лейтмотив. Лейтмотив в характеристике фильма 13.9 KB
  Лейтмотив. Лейтмотив в характеристике фильма. Одной из наиболее полных и интересных драматургических функций звука является звуковой лейтмотив. Лейтмотив сопровождает обычно либо неоднократное появление действующего лица либо повторение того или иного события. В к...
14261. Передача национального колорита, эпохи через музыку 13.44 KB
  Передача национального колорита эпохи через музыку. Киномузыка участвующая в синтетическом целом произведения иногда может представлять свое собственное изображаемое время то есть не то время которое показано кинокадром. При различных ситуациях связанных с фабул
14262. Музыка и юмор, ирония, пародия, манера исполнения 13.58 KB
  Музыка и юмор ирония пародия манера исполнения. Музыка не может шутить ни над чем кроме самой музыки. Композитор подсмеивается над своей музыкой или над музыкой другого композитора. В распоряжении композитора тысячи способов сделать музыку смешной. Он может неожида
14263. Музыкальная драматургия театральных постановок (музыкально-драматический спектакль) 14.64 KB
  Музыкальная драматургия театральных постановок музыкальнодраматический спектакль. Музыкальной драматургией называется комплекс музыкальных выразительных средств которые раскрывают идейное содержание спектакля создают характерные образы действующих лиц показ
14264. Музыкальная драматургия оперы 14.96 KB
  Музыкальная драматургия оперы. Опера по определению А. Н. Серова это сценическое представление в котором происходящее на сцене действие выражается музыкою т. е. пением действующих лиц отдельно каждого или вместе или хором и силами оркестра в бесконечно разнообразн
14265. Музыкальная драматургия балета 13.73 KB
  Музыкальная драматургия балета. В основе муз. Д. лежат общие законы драмы как одного из видов исква: наличие ясно выраженного центр. конфликта раскрывающегося в борьбе сил действия и противодействия определённая последовательность этапов раскрытия драм. замысла эксп...