10045

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

Доклад

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

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

Русский

2013-03-20

46 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

70775. Определение коэффициента вязкости жидкости методом Стокса 170.5 KB
  Цель работы: Изучить явление переноса на примере внутреннего трения; определить динамический и кинематический коэффициент вязкости жидкости. Для явления внутреннего трения справедлив закон Ньютона: градиент скорости динамический коэффициент вязкости...
70776. Изучение основных схем включения операционных усилителей 125.5 KB
  ОУ выполняются в виде интегральной полупроводниковой микросхемы которая содержит несколько транзисторных каскадов усиления напряжения причем входной каскад всегда выполняется по дифференциальной параллельно-симметричной схеме выходной каскад усиления тока и цепи...
70777. Исследование входных и выходных характеристик транзисторов 104.5 KB
  Для данного транзистора используя справочные данные определить тип цоколевку и выписать эксплуатационные параметры. Составить принципиальную схему для исследования входных и выходных характеристик транзистора в схеме с общим эмиттером с учетом его структуры.
70778. Исследование диаграмм срыва и нагрузочных характеристик автогенератора 157.5 KB
  В начале данной лабораторной работы были сняты зависимости амплитуды переменного напряжения на управляющем электроде затворе полевого транзистора от напряжения смещения при двух коэффициентов включения К1=15 и К2=05.
70779. ЛИНЕЙНЫЕ ЭЛЕКТРИЧЕСКИЕ ЦЕПИ 912 KB
  В него включены лабораторные работы по следующим разделам курса ТОЭ: переходные процессы в электрических цепях нелинейные электрические цепи теория электромагнитного поля. Сборку электрической цепи рекомендуется производить в следующей последовательности...
70783. Введение в UNIX 98.45 KB
  Цель первого занятия –на практике изучить или повторить если эта тема уже освещалась в курсе Операционные системы основные команды и утилиты UNIXподобных операционных систем. программы команды Основные команды.