10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

35139. Поддержка сложных запросов в файл-серверной информационной системе с использованием технологий Borland 59.5 KB
  Способным работать независимо от того отсутствуют ли требуемые таблицы или наличествуют и заполнены данными. Например: SELECT fio FROM stud; выборка поля fio из всех записей таблицы stud SELECT fio n_spect FROM stud; выборка полей fio n_spect из таблицы stud SELECT FROM stud; выборка всех полей из таблицы stud SELECT s. FROM stud S s; выборка всех полей из таблицы stud с присваиванием таблице псевдонима s SELECT s.n_spect S spect FROM stud S s; выборка из таблицы stud полей fio и n_spect с присваиванием им...
35140. Использование встроенных средств SQL-сервера InterBase для создания и использования базы данных 127 KB
  оздание БД интерфейсными средствами WISQL. Выполняется путем использования функции WISQL File Create Database. Диалог создания БД показан на рисунке 1. В поле Location Info устанавливается переключатель Local Engine
35142. Программная реализация выборки и модификации данных в базе данных Interbase 56.5 KB
  При этом сохранение результатов редактирования выполняется путем вызова рассмотренной ранее функции pplyUpdtes класса TBDEDtSet и всех его потомков например компонента Query содержимое выборки которого редактируется и кэшируется которая выполняет отправку в БД закэшированных на клиентской стороне изменений. Пример реализации функции обработки события OnUpdteRecord: void __fstcll TDtModule1::Query1UpdteRecordTDtSet DtSet TUpdteKind UpdteKind TUpdtection Updtection { switch UpdteKind { cse ukModify: brek; cse ukInsert:...
35143. АИС Магазин бытовой техники и электроники 419.63 KB
  Проектирование функциональных особенностей системы 5. Требуется создание информационной системы использование которой будет способствовать повышению эффективности работы всех отделов компании и обеспечивать ведение учета в единой системе. В расчетном задании предполагается осуществить представление информационной системы которая будет вести реестр создавать отчеты и генерировать заказы. Иметь оперативную связь между всеми пользователями системы содержать все необходимые данные о технике.
35144. Создание и заполнение справочников 8.26 MB
  Выполнить действия: А Выбрать пункт меню Справочник щелчком левой кнопки мыши Б Выбрать команду Фирмы щелчком левой кнопки мыши если разрешен учет по нескольким фирмам В Нажать клавишу SHIFTENTER для ввода новой фирмы Астра Г Заполнить реквизиты фирмы 2. Выполнить действия: А Выбрать пункт меню Справочник щелчком левой кнопки мыши Б Выбрать команду Места хранения щелчком левой кнопки мыши В Нажать клавишу Insert для ввода нового элемента Г в пункте Тип выбрать Склад Д в пункте Вид склада выбрать Склад оптовый Е Можно ввести...
35145. Ввод начальных остатков 2.75 MB
  12 в пункте Сумма: ничего не вводим в пункте Содержание операции: ввести для чего предназначена данная операция и Enter 4 Переходим к заполнению табличной части: А введем остатки по уставному фонду для Кливер и Русь колонка Дт это дебет счета. Из выпадающего меню выбираем счет 00 это специально придуманный счет используемый только для введения остатков в данной программе и ENTER ENTER колонка Кт это кредит счета. Из выпадающего меню выбираем счет 40 Уставной фонд и ENTER ENTER колонка СубконтоКт это объект...
35146. Учет поступления материальных ценностей 16.32 MB
  Д в пункте Поставщик Контрагент из выпадающего меню выбрать группу Поставщики а затем элемент Ротонда Е в пункте Примечание можно дать краткую характеристику о вводимой информации Ж в пункте Номер счета поставщика задать номер З перейдем к заполнению табличной части: в колонке ТМЦ справочник номенклатура выбрать группу Товары элемент Костюм женский в колонке Ед. выбрать шт в колонке Колво ввести 31 все остальные колонки заполнятся автоматические ввести также товары костюм мужской и пиджак мужской и ОК И в результате...
35147. Информационные системы. Общие сведения 10.58 MB
  К средствам извлечения информации относятся: штатные средства ручного ввода клавиатура мышь; средства автоматизированного ввода с твердых копий сканеры; специализированные средства ручного ввода дигитайзеры световые перья сенсорные экраны; средства ввода речевой информации; средства ввода данных с аппаратуры датчики измерительные устройства аппаратура связи. Это программное обеспечение может быть как достаточно простым и предполагать только передачу операционной системе данных от аппаратных компонентов так и сложным...