10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

45537. Источники и методы сбора информации в журналистике и PR. Характеристики PR-информации 36.5 KB
  Характеристики PRинформации. Типы информации: межличностная информация обеспечивающая коммуникацию двух и более лиц и носящая непубличный характер. ПР информация – разновидность социальнйо информации инициированная базисным субъектом ПР представляющая в оптимизированном виде факты деятельности данного субъекта.
45538. Медиарилейшнз: современное состояние 46.5 KB
  выступает как менеджер автор и организатор донного проекта информационный ПР ориентирован на работу со СМИ т. МР ШИШКИНА – социальные практики направленные на оптимизацию взаимодействия субъекта ПР базисный кто заказывает или технологический – кто исполняет со СМИ. В США МР взяли основу еще во времена президента Джексона когда бывший журналист и репортёр Кендел стал исполнять функции пресссекретаря: писал статьи для СМИ.ленинградский советов появились отделы по связям со СМИэто портотипы будущих ПРслужб.
45539. Пресс-служба и ее функции 69 KB
  Пресс-служба и ее функции Пресс-служба – автономная структурная единица субъекта PR осуществляющая функции медиарилейшнз. Крупные организации и компании имеют собственные пресс-службы в небольших организациях эта функция может совмещаться с другими функциями исполнителя. Штат прессслужбы может составлять различное количество людей – от одногодвух до 20ти и более. Специалисты прессслужб должны регулировать отношения между своей организацией и СМИ поддерживать информационный баланс двустороннего информационного взаимодействия.
45540. Классификация PR-текстов и система жанров PR-текста 47.5 KB
  Чем же пиартекст принципиально отличается от журналистского и рекламного Рекламный попадает на платные страницы. А пиартекст умело мимикрирует под текст новостийный. Здесь полезно знать что пиар иногда определяют как ориентированную журналистику поскольку в пиартексте присутствуют всегда тщательно отобранные и соответствующим образом скомпонованные факты. Пиаринформация – это тип социальной информации которая производится в процессе деятельности социального субъекта фирмы организации персоны – базисного субъекта пиар...
45541. Типология корпоративных изданий 36 KB
  Типология корпоративных изданий Корпорация – человеческие и финансовые ресурсы общая цель профессиональные интересы идентификация Печатные методы PR: Фирменный журнал Многотиражная газета Информационный бюллетень Письмо Прессбук – результат мониторинга в сброшюрированном виде для руководителя Отчет Корпоративная реклама Корпоративные документы кодексы относит к корпоративным изданиям по форме – журналы газеты и информационные бюллетени. Что такое корпоративное издание Это периодическое издание журнал газета...
45542. Спичрайтинг как технология 41 KB
  специфическая PRтехнология представленная в виде техники подготовки и написания текста предназначенного для устного исполнения а также консалтинг первого должностного лица по организации публичного выступления и его исполнению. – учебная дисциплина раздел деловой риторики Спичрайтер – лицо занимающееся профессиональной PRдеятельностью по составлению текста устного публичного выступления для первого лица и консалтингу касающемуся организации и исполнения публичного выступления. Цели публичного выступления: информирование улучшение...
45543. Слоган в политических и корпоративных маркетинговых коммуникациях 59.5 KB
  СЛОГАН: Понятийный аппарат: Слоган – четкая ясная и сжатая формулировка рекламной идеи которая воспринимается и запоминается. Ачкасова Слоган – спрессованная до формулы суть рекламной концепции доведенная до лингвистического совершенства запоминающаяся мысль. Феофанов Слоган фирменный лозунг представляет собой постоянно используемый оригинальный фирменный девиз.Иванова Слово слоган произошло от гаэльского означавшего в древности воинственный призыв к бою.
45544. Политический имидж 43.5 KB
  Политический имидж Структурная модель политического лидера ЕгороваГантман Пятичленная модель Персональные характеристики психофизические – активность агрессивность сила мощь; характер тип личности стиль принятия решений; локус контроля психологическая интенция индивида на восприятие им ситуации контроля значимых для него ситуаций внутренний – сам всё контролирует; внешний – фаталист; личные коммуникативные характеристики Социальные характеристики модель ролевого поведения – по Берну человеческие качества социальный и...
45545. Имидж организации 39 KB
  Имидж организации Имидж – целенаправленно сформированный образ субъекта ПР персоны корпорации выделющий определённые ценностные характеристики призванный оказать эмоциональнопсихололгическое воздействие на определённую группу ЦО. Имидж – форма. Конечным результатом PRдеятельности является формирование стойкого социальнопсихологического стереотипа под названием ИМИДЖ. Образ непроизвольный и имидж конструируется специально и целенаправленно.