10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

25772. Анализ производства продукции и ее качества 34 KB
  Объем производства и реализации продукции может выражаться в натуральных условнонатуральных трудовых и стоимостных измерителях. Обобщающие показатели объема производства продукции получают с помощью стоимостной оценки. Валовая продукция это стоимость всей произведенной продукции и выполненных работ включая незавершенное производство.
25773. Анализ состава и движения капитала организации 32 KB
  Величина уставного капитала объявляется при регистрации предприятия а при корректировке его величины требуется перерегистрация учредительных документов. Основным источником пополнения собственного капитала является нераспределенная прибыль предприятия. В процессе анализа необходимо детально изучить динамику и структуру собственного и заемного капитала выяснить причины изменения его отдельных слагаемых и оценить их за отчетный период.
25774. Анализ состояния расчетов с дебиторами и кредиторами 33 KB
  Несоблюдение договорной и расчетной дисциплины несвоевременное предъявление претензий по возникающим долгам приводят к значительному росту задолженности как дебиторской так и кредиторской к нестабильности финансового состояния. Анализ дебиторской задолженности и оценка ее реальной стоимости заключается в анализе задолженности по срокам ее возникновения в выявлении безнадежной задолженности и формировании на эту сумму резерва по сомнительным долгам. Анализ состояния дебиторской задолженности начинают с общей оценки динамики ее объема в...
25775. Звук: основные характеристики, свойства, распространение в среде 15.97 KB
  Сила звука зависит от величины амплитуды колебаний. чем шире размах колебаний тем звук сильнее и наоборот чем меньше размах тем меньше сила звука Высота звука зависит от частоты колебаний звучащего тела и измеряется числом полных колебаний в секунду. Тембр звука. Тембром или окраской звука называют то его свойство благодаря которому можно отличить друг от друга одинаковые по интенсивности и по высоте звуки издаваемые разными источниками.
25776. Звукопроводящий отдел слухового анализатора. Понятие о воздушном и костном звукопроведении 14.35 KB
  Звукопроведение может осуществляться 2 путями: воздушный путь; костный путь. В норме основной путь звукопроведения – воздушный. Его поступление во внутреннее ухо осуществляется через ушную раковину и наружный слуховой проход барабанную полость и систему слуховых косточек воздушный путь звукопроведения где происходит усиление энергии звуковой волны. Звук также может проходить непосредственно через костные образования височной кости к кортиевому органу костный путь звукопроведения.
25777. Звуковосприятие теории слуха: резонансная, гидродинамическая, микрофонного эффекта улитки, цитохимическая 14.93 KB
  Звуковосприятие теории слуха: резонансная гидродинамическая микрофонного эффекта улитки цитохимическая. На верхнем завитке улитки натянуты длинные струны которые резонируют на низкие звуки. Гидродинамическая теория автор Бекеши её суть: При звуковосприятии на основной мембране улитки происходят сложные гидродинамические процессы. Микрофонный эффект улитки автор Уивер Брэй её суть: Улитка работает по принципу микрофона т.
25778. Методы исследования слуховой функции 12.72 KB
  Методы исследования слуховой функции Основной задачей исследования слуха является определение остроты слуха т. Методы исследования слуха: 1. субъективные предполагают активное участие ребенка: исследование слуха камертонами. Результат исследования слуха аудиометром представляется обычно в виде аудиограммы На специальную аудиометрическую сетку на которой по горизонтали откладываются звуковые частоты Гц по вертикали уровни громкости соответствующих звуков в децибелах наносятся в виде точек показания аудиометра для каждого уха...
25779. Слуховое утомление и слуховая адаптация 14.58 KB
  Минимальная сила звука называется порогом слухового ощущения. Сила звука при которой нарастание громкости звука прекращается и появляется ощущение давления или даже боли в ухе называется болевым порогом.
25780. Причины стойких нарушений слуха: врождённые и приобретенные 14.96 KB
  Причины стойких нарушений слуха: врождённые и приобретенные. Во всех случаях к значительному и стойкому понижению слуха ведет лишь полное заращение наружного слухового прохода. При атрезии наружного слухового прохода понижение слуха носит характер поражения звукопроводящего аппарата т. страдает главным образом восприятие низких звуков; восприятие высоких тонов сохраняется костная проводимость остается нормальной или даже несколько улучшается Приобретенные нарушения слуха возникают от разнообразных причин.