10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

14313. Исследование электрических процессов в переходных цепях. Явления дифференцирования и интегрирования 67.5 KB
  PAGE 1 Отчет по лабораторной работе №10в Тема: Исследование электрических процессов в переходных цепях. Явления дифференцирования и интегрирования. Задача Исследовать электрические процессы в переходных цепях. Познакомиться с явлениями диф
14314. Молекулярна фізика. Термодинаміка 1.32 MB
  Молекулярна фізика. Статистична фізика. Дослідні газові закони. Закони для суміші газів. Внутрішня енергія газу та перший закон термодинаміки. Приклади розвязання задач. Запитання для самоконтролю. Задачі для роботи в аудиторії. Задачі для самостійної роботи. Колові процеси та реальні гази...
14315. Визначення вологості атмосферного повітря 81 KB
  Лабораторна робота №10 Визначення вологості атмосферного повітря Мета роботи: Визначити абсолютну і відносну вологість повітря психрометром Августа. Обладнання: 1 .Психрометр Августа колба з дистильованою водою таблиця тиску насиченої водяної пари при різ
14316. Визначення коефіцієнта поверхневого натягу методом відриву краплі 54.5 KB
  Лабораторна робота №9 Визначення коефіцієнта поверхневого натягу методом відриву краплі Мета роботи : 1. Вивчити явище поверхневого натягу; 2. Визначити коефіцієнт поверхневого натягу рідині. Прилади та обладнання : Скляна бюретка з краном. К
14317. Визначення коефіцієнта Пуассона газу методом адіабатичного розширення 68 KB
  Лабораторна робота №11 Визначення коефіцієнта Пуассона газу методом адіабатичного розширення Обладнання Установка для визначення коефіцієнта Пуассона газу методом адіабатичного розширення Метод вимірювання і опис у
14318. Вивчення коефіцієнта в'язкості рідини методом Стокса 97 KB
  Лабораторна робота № 8 Вивчення коефіцієнта вязкості рідини методом Стокса Мета роботи: 1. Вивчити механізм явища переносу внутрішнє тертя. 2. Визначити коефіцієнт внутрішнього тертя рідин за швидкістю падіння кульки. Прилади та матеріали: Скляний ци
14319. Молекулярна фізика 5.27 MB
  ФІЗИКА Методичні рекомендації до модуля 3 €œМолекулярна фізика€ для виконання лабораторних робіт студентами денної та заочної форм навчання напрямів підготовки: 6.100102 €œПроцеси машини та обладнання в агропромисловому виробництві€ 6.010104 €œПрофесійн...
14320. Внутрішній фотоефект у напівпровідниках 58 KB
  Лабораторна робота № 12 Внутрішній фотоефект у напівпровідниках Мета роботи: експериментально встановити залежність опору напівпровідника від величини падаючого на нього потоку електромагнітного випромінювання та визначити чутливість фото резистора. Прилади та о...
14321. Визначення опору методом мостової схеми 63 KB
  Лабораторна робота №3 Визначення опору методом мостової схеми Мета роботи: Вивчити метод мостової схеми і визначити невідомі опори цим методом. Прилади і приналежності: відомий опір R=470 Ом невідомі опори Rx1 Rx2 Rx3; реохорд і гальванометр нульіндикатор; джерело по...