10045

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

Доклад

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

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

Русский

2013-03-20

46 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

37940. ОПРЕДЕЛЕНИЕ УСКОРЕНИЯ СВОБОДНОГО ПАДЕНИЯ С ПОМОЩЬЮ ФИЗИЧЕСКОГО И МАТЕМАТИЧЕСКОГО МАЯТНИКОВ 166.5 KB
  Определение ускорения свободного падения с помощью математического маятника. Определение ускорения свободного падения с помощью оборотного маятника.Определение ускорения свободного падения с помощью математического маятника.Определение ускорения свободного падения с помощью оборотного маятника.
37941. ИЗУЧЕНИЕ КОЛЕБАНИЙ ПРУЖИННОГО МАЯТНИКА 168.5 KB
  11 Изучение свободных незатухающих колебаний пружинного маятника.11 Изучение затухающих колебаний пружинного маятника12 5. Изучение вынужденных колебаний пружинного маятника.14 ЛАБОРАТОРНАЯ РАБОТА № 10 ИЗУЧЕНИЕ КОЛЕБАНИЙ ПРУЖИННОГО МАЯТНИКА Цель работы Изучение свободных незатухающих свободных затухающих и вынужденных колебаний пружинного маятника.
37942. Изучение собственных колебаний струны 137 KB
  Колебания струны5 3.10 Лабораторная работа № 11 а Изучение собственных колебаний струны 1. Цель работы Изучение собственных колебаний струны. Колебания струны В закрепленной с обоих концов натянутой струне при возбуждении поперечных колебаний устанавливаются стоячие волны причем в местах закрепления струны должны располагаться узлы.
37943. Определение ускорения силы тяжести при свободном падении тела 374 KB
  Центростремительное ускорение соответствующее движению Земли по орбите годичное вращение гораздо меньше чем центростремительное ускорение связанное с суточным вращением Земли. Поэтому с достаточной точностью можно считать что система отсчета связанная с Землей вращается относительно инерциальных систем с постоянной угловой скоростью суточного t = 86400 с вращения Земли . Если не учитывать вращение Земли то тело лежащее на ее поверхности следует рассматривать как покоящееся сумма действующих на это тело сил равнялось бы тогда...
37944. Изучение закона сохранения энергии с помощью маятника Максвелла 188 KB
  12 Лабораторная работа № 13 Изучение закона сохранения энергии с помощью маятника Максвелла 1. Цель работы Изучение закона сохранения энергии на примере движения маятника Максвелла. Диск маятника представляет собой непосредственно сам диск и сменные кольца которые закрепляются на диске. При освобождении маятника диск начинает движение: поступательное вниз и вращательное вокруг своей оси симметрии.
37945. НАКЛОННЫЙ МАЯТНИК 252 KB
  Изучение силы трения качения. Определение коэффициента трения качения. Со стороны поверхности на тело действует сила трения FТР. Тело скользит по поверхности со скоростью на него действует сила трения совершающая отрицательную работу вследствие чего полная механическая энергия системы уменьшается т.
37946. Изучение закона сохранения момента импульса с помощью гироскопа и определение скорости его прецессии 695 KB
  12 Лабораторная работа № 15 Изучение закона сохранения момента импульса с помощью гироскопа и определение скорости его прецессии 1. Цель работы Изучение гироскопического эффекта и закона сохранения момента импульса с помощью гироскопа. Определение скорости прецессии гироскопа измерение угловой скорости вращения маховика гироскопа и момента инерции гироскопа. Справедливость этого закона можно проверить с помощью гироскопа.
37947. Определение коэффициента Пуассона воздуха методом адиабати 445 KB
  1 Определение коэффициента Пуассона воздуха методом адиабатического расширения: Методические указания к лабораторной работе № 16 по курсу общей физики Уфимск. В работе определяется коэффициент Пуассона воздуха методом адиабатического расширения основанным на измерении давления газа в сосуде после последовательно происходящих процессов его адиабатического расширения и изохорного нагревания.8] Список литературы ЛАБОРАТОРНАЯ РАБОТА № 16 ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ПУАССОНА ВОЗДУХА МЕТОДОМ АДИАБАТИЧЕСКОГО РАСШИРЕНИЯ 1. Цель работы Определение...
37948. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА УРАВНЕНИЯ СОСТОЯНИЯ И ЗАКОНОВ ИДЕАЛЬНОГО ГАЗА 146.5 KB
  1 Экспериментальная проверка уравнения состояния и законов идеального газа: Методические указания к лабораторной работе № 17 по курсу общей физики Уфимск. В работе изучается взаимосвязь параметров задающих состояние идеального газа и закономерности их изменения. Контрольные вопросы [7] Список литературы ЛАБОРАТОРНАЯ РАБОТА № 17 ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА УРАВНЕНИЯ СОСТОЯНИЯ И ЗАКОНОВ ИДЕАЛЬНОГО ГАЗА 1.