10045

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

Доклад

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

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

Русский

2013-03-20

46 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

69646. Творчий проект: Таця 7.59 MB
  Перші підноси були величезними - розміром зі стіл, називалися «скатертними» і призначалися для багатьох страв. Потім їх розміри поступово зменшилися. Якщо ж шлях від кухні до їдальні порівняно довгий, необхідно використати підноси з прорізами або ручками.
69647. Виготовлення настінного календаря 576 KB
  Розробка технічного завдання Призначення виробу. Настінний календар призначений для повсякденного використання в побуті та на робочих місцях. Основними вимогами повинні бути практичність та естетичний вигляд.
69648. ОБРЯДОВИЙ РУШНИК 342 KB
  Експлуатаційні показники застосування виробу виду роботи на практиці виходячи призначення виробу цей рушник використовується при обряді хрещення а також функція оберегу. Вплив виробу на якість і ефективність реалізації ним експлуатаційних показників рушник є оберегом для дитини...
69649. Виготовлення іграшкової машинки 1.4 MB
  Розробка технічного завдання Призначення виробу. Цей виріб призначено для дітей віком від 6 до 10 років, Вимоги до матеріалів. Матеріали повинні бути екологічно чисті та нешкідливі для дітей. Ще Машинку треба зробити так щоб дитина ненароком не проковтнула яку не будь деталь...
69650. Розробка творчого проекту на виготовлення декоративної тарелі 5.49 MB
  Призначення проектованого виробу: У наш час декоративні тарелі можна використовувати як посуд для святкового столу що слугує для подання печива цукерок солодощів горіхів різноманітних фруктів а також для підношення на весіллі чарок з напоями медом вином хлібасолі тощо.
69653. Гідравліка 123.5 KB
  Знайти: Абсолютний тиск Р1 перед входом в насос якщо подача насоса Q довжина трубопроводу l1 його діаметр d1 Надлишковий тиск в бензосховищі P=const.; Потрібний напор насоса якщо манометричний тиск в трійнику рівний P2 довжина трубопроводу l2 його діаметр d2...