10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

7314. Колективний договір. Контроль за виконанням колективного договору і види відповідальності 106 KB
  Колективний договір План Поняття колективного договору. Колективні переговори по укладенню колективного договору. Порядок укладення колективного договору і його зміст. Контроль за виконанням колективного договору і види відповідальності ...
7315. Керування пам’яттю в ОС. Простий безперервний розподіл і розподіл з перекриттям. Розподіл пам’яті статичними й динамічними розділами 121.5 KB
  Тема: Керування памяттю в ОС. Простий безперервний розподіл і розподіл з перекриттям. Розподіл памяті статичними й динамічними розділами План Основна память. Вимоги до адрес, використовуваних у програмах...
7316. Процесуальні строки і витрати 40.16 KB
  Процесуальні строки і витрати ПЛАН: Вступ. Поняття процесуальних строків та їх значення у кримінальному процесі. Класифікація строків у кримінальному процесі. Порядок обчислення процесуальних строків. Поняття і види процесуальних в...
7317. Розв’язування систем лінійних алгебраїчних рівнянь над скінченними полями 184.63 KB
  Ю.Д. Жданова. Лекції з ВГПМ. М2 ТЧ обчислювальні алгоритми. Лекція № 7 10 Тема: Розв’язування систем лінійних алгебраїчних рівнянь над скінченними полями План лекції: Алгоритм знаходження всіх цілочислових розв’язків лінійного а...
7318. Організаційні та правові основи захисту населення під час воєнних дій. Правила поводження населення в конкретних НС 63.5 KB
  Тема: Організаційні та правові основи захисту населення під час воєнних дій. Правила поводження населення в конкретних НС. План: Основні положення міжнародного права з питань захисту людей. Правила поводження населення в конкретних НС. Ве...
7319. Взаємовідносини у колективі 97.5 KB
  Взаємовідносини у колективі План Прийняття групового рішення. Соціально - психологічний клімат колективу. Одним із показників успішної діяльності керівника організації (фірми, колективу) є рівень сформованості соціально-психологічно...
7320. Основи психокорекції. Курс лекцій 264.5 KB
  Психокорекційна практика як основна форма діяльності практичного психолога Поняття про психологічну корекцію. Мета і завдання психокорекції. Принципи психокорекційної роботи: принцип єдності діагностики і кор...
7321. Тістечка. Напівфабрикати для приготування тістечок 45.5 KB
  Тістечка. Напівфабрикати для приготування тістечок. Класифікація тістечок. Особливості технології приготування тістечок. Основні органолептичні показники. Санітарні правила при приготуванні та реалізації. Умови та термін зберігання...
7322. Робочий час і час відпочинку 205 KB
  Як відомо, ні рабовласницький, ні феодальний устрої не мали законодавчого обмеження робочого часу, оскільки носій робочої сили був разом з іншими знаряддями виробництва об'єктом власності.