10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

77583. Организационный этап формирования системы менеджмента качества 79.5 KB
  Реализация предварительного цикла работ по формированию СМК. Создание организационной структуры СМК. Реализация предварительного цикла работ по формированию СМК Непосредственно процессу разработки и внедрения СМК предшествует организационный этап основным назначением...
77584. ФОРМИРОВАНИЕ ПРОЦЕССНОЙ МОДЕЛИ СМК 172.5 KB
  Определить состав документации устанавливающий требования ограничения и рекомендации необходимые для результативного выполнения процесса. Определить показатели и спланировать качество и результативность процесса.
77585. Разработка документации СМК 122.5 KB
  Существует еще одна категория, неявно упоминаемая в стандарте. Это - специальные формы. Назначение этих форм - предоставить руководящие указания или инструктировать относительно регистрации данных по качеству, в частности, какую информацию следует заносить в них.
77586. Содержание обязательных документированных процедур 83.5 KB
  В каждой организации, независимо от того, намерена ли она внедрять СМК или нет, существует документооборот и соответствующие инструкции по делопроизводству, описывающие порядок управления внутренними и внешними документами.
77587. Внедрение и опытная апробация СМК 39 KB
  Внедрение СМК может начинаться с издания приказа о введении в действие документов СМК. Датой введения в действие СМК считается дата утверждения Политики, Руководства по качеству и процедуры по разработке и введению в действие внутренних документов.
77588. ТЕХНИКА И ПРОГРАММИРОВАНИЕ В ЭКОЛОГИИ 719.5 KB
  Стремительный рост общей численности населения планеты совместно с усилением техногенных воздействий на окружающую среду существенно меняют ход глобальных природных процессов на Земле.
77589. Триггеры. Не тактируемые и тактируемые триггеры 231 KB
  Устройство имеющее два устойчивых состояния называют триггером. С приходом переключающих запускающих сигналов переход триггера из одного состояния в другое происходит лавинообразно и потенциалы на выходах меняются на противоположные.
77590. Андрей Тимофеевич Болотов 53.56 KB
  Так, например, обстоит дело с определением места в истории нашей страны Андрея Тимофеевича Болотова. Выдающийся деятель, внесший неоценимый вклад в развитие науки и культуры, основоположник русской сельскохозяйственной науки, к сожалению, до сих пор не получил должного признания своих заслуг.
77591. Тэер Альбрехт Даниель (1752-1828) - немецкий агроном. Автор гумусовой теории питания растений 224.26 KB
  Альбрехт Тэер родился 14 мая 1752 года в семье врача, служившего при дворе ганноверского курфюрста. В молодости пошёл по стопам отца, окончил медицинский факультет университета в Гёттингене (1774). По возвращении в родной Целле получил по наследству должность личного врача курфюрста Ганновера Георга III.