10045

Тестирование чисел на простоту, случайные и детерминированные тесты. Тест малой теоремы Ферма

Доклад

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

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

Русский

2013-03-20

46 KB

23 чел.

Тестирование чисел на простоту, случайные и детерминированные тесты. Тест малой теоремы Ферма

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

Соответствующие вычислительные процедуры включают в себя алгоритмы, реализующие этап тестирования чисел на простоту.

В криптографической практике подобные алгоритмы носят название тестов. В основе тестов лежат т.н. критерии простоты.

Существует два типа критериев простоты: детерминированные и вероятностные. Детерминированные тесты позволяют доказать, что тестируемое число – простое.

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

Детерминированные тесты более полезны, когда необходимо построить большое простое число, а не проверить простоту, скажем, некоторого единственного числа.

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

Примером вероятностного теста является тест на основе малой теоремы Ферма. Эта теорема утверждает, что если - простое, то для всех , взаимно простых с , выполняется условие (сравнение Ферма): . Таким образом, если условие теоремы Ферма не выполнено хотя бы для одного числа в интервале , то - составное.

Тест на основе малой теоремы Ферма заключается в следующем.

Псевдослучайно выбираем вычет , проверяем условие . Если условие не выполнено, значит, - составное. Проверяем сравнение Ферма (критерий простоты). Если оно не выполняется, то число - составное. Иначе, повторяем тест для другого значения и так далее. Тест может давать неверные результаты, т.к. существуют составные числа , для которых, при некотором выполняется условие малой теоремы Ферма, например, .

Назовем нечетное составное число псевдопростым по основанию  , если пара удовлетворяет сравнению .

Можно показать, что если существует (вообще говоря, неизвестное) основание , по которому не является псевдопростым, то при повторении теста Ферма  вероятность -кратного выполнения сравнения равна . В этом случае вероятность ошибки теста стремится к нулю с увеличением .

Следовательно, вероятность ошибки может не снижаться, лишь если является псевдопростым для всех (ненулевых) оснований. Тем не менее, такие числа существуют. Они называются числами Кармайкла. Например, числом Кармайкла является число .

Следовательно, тесту Ферма, вообще говоря, доверять нельзя. Однако этот тест является состовной частью ряда других тестов на простоту, т.к. его проверочное условие является необходимым условием простоты числа n.


 

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

77204. Автоматизация отслеживания состояния покрытия автомобильных дорог 249.5 KB
  Общеизвестно что состояние дорожного покрытия на протяжённых участках автомобильных дорог как на территории Российской Федерации так и в некоторых других странах далеко от идеального. Характер и численность дефектов покрытия разнятся: на некоторых участках автомобилист может столкнуться...
77205. Декомпозиция временных рядов в СУБД Oracle 102 KB
  Целью данной работы являлось создание пакета процедур и функций с помощью которых можно было бы легко и эффективно манипулировать временными рядами в СУБД ORCLE. Для хранения информации о рядах создает отдельная таблица Timeseries в которой хранятся имя или идентификатор ряда...
77206. Разработка программного обеспечения системы программно-аппаратной защиты ПО 381.5 KB
  Данная курсовая работа является частью проекта по разработке системы программно-аппаратной защиты ПО. Данный комплекс представляет собой комбинированную систему, предназначенную для защиты коммерческого программного обеспечения от несанкционированного использования или для защиты...
77208. Поддержка языка Lisa в среде Eclipse 293 KB
  В компании Parallels ведётся разработка продукта StellArt IDE – среда программирования на основе Eclipse для языка Lisa. Я участвую в разработки данного продукта. Продукт разрабатывается по технологии Scrum, так что каждый месяц в течение всего периода разработки поставляется...
77209. Инструмент аспектно-ориентированного программирования Aspect.Java 628 KB
  Данная курсовая работа посвящена такой относительно новой методологии в разработке программного обеспечения как аспектно-ориентированное программирование. Суть данного подхода – поддержка разработки и модификации сквозной функциональности (cross-cutting concerns) в больших программных системах.
77210. Разработка framework для JSR 290 TCK 450 KB
  Technology Compatibility Kit (TCK) – тестовая сюита, позволяющая протестировать реализацию какого-либо Java Specification Request (JSR) на соответствие спецификации. Это одна из трех составляющих ратифицированного JSR в Java Community Process, которыми являются: Спецификация JSR JSR Reference Implementation
77211. АКТОРНОЕ РАСШИРЕНИЕ ЯЗЫКА JAVA В СРЕДЕ MPS 243 KB
  В качестве средства создания расширения была выбрана среда мета-программирования MPS что позволило автоматически получить интегрированные средства разработки для применения расширения и кроме того достичь совместимости с другими языковыми расширениями созданными в среде MPS. Название средства Совместимость расширений Языковая инфраструктура LISP Есть Нет Внутренние языки в Ruby Groovy Есть Нет XText frmework Нет Есть...
77212. Исследование работы с географическими данными в Oracle 10g 482.5 KB
  Спроектировать базу данных с учетом специфики хранимой информации; Перенести собранную обо всех электростанциях информацию в БД; Разработка интерфейса администратора для мониторинга и управления информационной системой.