10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

4337. Cascading Style Sheet (CSS) в примерах 730.5 KB
  CascadingStyleSheet в примерах Назначение CSS Дизайн Web-узлов — это точное размещение компонентов HTML-страниц относительно друг друга в рабочей области окна браузера. Недостатки такого определения Web-дизайна очевидны. В нем не уч...
4338. CSS – каскадные таблицы стилей 50.5 KB
  CSS – каскадные таблицы стилей CSS – CascadingStyleSheets (каскадные таблицы стилей). Стили определяют отображение элементов HTML HTML – для логической разметки документа (заголовки, параграфы, списки). Браузеры стали ввод...
4339. Использование JavaScript в HTML 64.5 KB
  JavaScript в HTML Основные тезисы: Не тоже самое, что и Java, хотя синтаксис немного схож. Скриптовый (облегченный) интерпретируемый язык без строгой типизации. Внедряется в HTML-код Поддерживается всеми ...
4340. Программирование для Web, CGI (Common Gateway Interface) 464 KB
  Программированиедля Web, CGI (Common Gateway Interface) CGI - это спецификация обмена данными между прикладной программой, выполняемой по запросу пользователя, и HTTP-сервером, который данную программу запускает. Часть информации заголовка HTT...
4341. Протокол HTTP. Унифицированные указатели ресурсов (URL) 133.5 KB
  Протокол HTTP В середине 90-х годов очень популярной стала WWW (WorldWideWeb) — Всемирная паутина. Это набор протоколов и программ для Интернета, представляющих информацию в гипертекстовом формате. Знаменитый браузер Mosaic...
4342. Создание приложений для динамического представления Web-страниц 235 KB
  Создание приложений для динамического представления Web-страниц Основы использования Web - технологий для доступа к базам данных Развитие web технологий с использованием баз данных Создание динамических сайтов Современные технологии динамического пр...
4343. Обзор Common Gateway Interface (CGI) 149.5 KB
  Обзор CGI CGI (Common Gateway Interface, общий шлюзовой интерфейс) относится к числу средств, без которых нельзя обойтись как при создании комплексных Web-узлов, так и при управлении ими. CGI обеспечивает возможность писать сценарии, котор...
4344. Расширенный язык разметки XML 244.5 KB
  Расширенный язык разметки XML Общие сведения об XML Особенности XML Стандарты XML Структура и элементы языка разметки XML Таблицы стилей Расширяемый язык создания ссылок Спецификация XForms 1.0 Области использования языка XML Общие сведения об XML К...
4345. Базовый процесс технологии проектирования веб-сайта и его фазы 87 KB
  Базовый процесс технологии проектирования веб-сайта и его фазы Базовый процесс - это всесторонний план работы для групп любых типов и компаний всех видов с различными бюджетами. Базовый процесс - это всего пять фаз, каждая фаза включает три переплет...