10045

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

Доклад

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

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

Русский

2013-03-20

46 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

13258. Изучение погрешностей измерений 261.5 KB
  Лабораторная работа № 1 Изучение погрешностей измерений Цель работы: Изучить погрешности измерений. Оценить погрешности измерения физических величин. Ход работы. 1. Теоретическая часть. 1.1. Физические измерения. Измерением в физике называется сравнени
13259. Погрешности измерений. Цели математической обработки результатов эксперимента 107 KB
  Погрешности измерений Основой всего естествознания является наблюдение и эксперимент. Наблюдение - это систематическое целенаправленное восприятие того или иного объекта или явления без воздействия на изучаемый объект или явление. Наблюдение позволяет получит...
13260. Исследование цепи постоянного тока 905 KB
  Лабораторная работа №1 по курсу электротехники ИССЛЕДОВАНИЕ ЦЕПИ ПОСТОЯННОГО ТОКА Лабораторная работа №1 Исследование цепи постоянного тока. Цель работы: Изучение методик измерения постоянного напряжения ток и сопротивления с помощью авометра и электронног
13261. Ознакомление с устройством и работой электронного осциллографа 2.54 MB
  ЛАБОРАТОРНАЯ РАБОТА 2. ИЗУЧЕНИЕ ЭЛЕКТРОННОГО ОСЦИЛЛОГРАФА Цель работы: ознакомление с устройством и работой электронного осциллографа. Приборы и принадлежности: универсальный стенд электронный осциллограф звуковой генератор. Введение Осциллограф предна
13262. Исследование цепей переменного тока 426.5 KB
  Лабораторная работа №3. Исследование цепей переменного тока Цель работы: изучение простейших цепей переменного тока и методик измерения их основных параметров. Приборы и принадлежности: Универсальный стенд. Вольтметр. Осциллограф. Амперметр. ...
13263. Исследование неразветвленной цепи переменного тока 2.98 MB
  Лабораторная работа № 4. Исследование неразветвленной цепи переменного тока. Цель работы: Исследование зависимостей параметров неразветвленной цепи переменного тока от частоты. Изучение резонанса напряжений. Приборы: 1. универсальный стенд. 2. ге...
13264. Исследование разветвлённой цепи переменного тока 1.04 MB
  Лабораторная работа № 5 Исследование разветвлённой цепи переменного тока. Цель работы: Исследование зависимостей параметров разветвлённой цепи переменного тока от частоты. Исследование резонанса токов.
13265. Измерение мощностей цепей переменного тока 2.52 MB
  Лабораторная работа №6. Измерение мощностей цепей переменного тока. Цель работы: изучение методов измерения активной реактивной полной мощности и коэффициента мощности в цепях содержащих R C и L.. Приборы: 1. Универсальный стенд; 2. Ваттметр; ...
13266. Ознакомление с устройством и принципом работы трансформатора 1.49 MB
  Лабораторная работа № 7 Исследование однофазного трансформатора. Цель: Ознакомление с устройством и принципом работы трансформатора. Получение основных характеристик трансформатора. Приборы: 1. Амперметр 2. Вольтметр ...