10045

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

Доклад

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

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

Русский

2013-03-20

46 KB

24 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

26674. ЗОЛОТОЕ КОЛЬЦО РОССИИ 98.88 KB
  МОСКВА Бывают городатруженики городакоммерсанты городаханжи городамузеи городавенценосцы . Так писал о городах К. В этих городах сочетаются уникальные памятники архитектуры скромная красота природы и гений человека его мастерство видение жизни и стремление украсить свой быт народные промыслы. Так что же входит в понятие Золотое Кольцо Это сама Москва и окружающие ее областные города: Ярославль Кострома Владимир Иваново и множество районных городов: Ростов Великий Суздаль ПереславльЗалесский Нерехта Плесс Палех...
26675. Концепция развития туризма в Архангельской области на 2011-2014 годы 25.12 KB
  Концепция разработана в рамках реализации Стратегии социальноэкономического развития Архангельской области до 2030 года.1999 № 14923ОЗ О туризме в Архангельской области; Стратегия социальноэкономического развития Архангельской области до 2030 года. Характеристика современной туристской индустрии Архангельской области 1.
26676. КОНЦЕПЦИЯ РАЗВИТИЯ МОЛОДЕЖНОГО ТУРИЗМА 34.24 KB
  Другой аспект туризма туристский бизнес. Настоящий бум развития туризма в нашей стране был в 30е и 60е годы прошлого века. В настоящее время отсутствует комплексный подход к развитию туризма в стране в 90е годы руководство туризмом было разведено по 14 ведомствам и частному капиталу.
26677. Наследование при моно- и дигибридном скрещивании 14.38 KB
  Закон доминирования первый закон Менделя − это закон единообразия гибридов первого поколения. Это соотношение выражает второй закон Менделя или закон расщепления признаков у гибридов второго поколения в соотношении 3:1 по фенотипу. Закон чистоты гамет гамета содержит 1 и только 1 аллель от каждого гена. 3й закон Менделя: закон независимого наследования.
26678. Полиплоидия. Автополиплоидия, её фенотипические эффекты и генетика. Амфидиплоидия как механизм получения плодовитых аллополиплоидов. Значение полиплоидии в эволюции и селекции растений 13.47 KB
  Геномные мутации это мутации затрагивающие число хромосом изменяющие геномгаплоидный набор хромосом с локализми в них генами. Полиплоидия это изменение числа хромосом кратное гаплоидному. Умножение одного и того же гаплоидного числа хромосом генома назся автополиплоидией. Различают полиплоидию сбалансую с чётным числом наборов хромосом и несбалансую с нечётным.
26679. Строение митотической хромосомы 11.76 KB
  Она связана с тонкими фибриллами и телом хромосомы в области перетяжки. Обычно хромосома имеет только 1 центромеру но может встречаться дицентрические и полицентрические. Те ке хромосомы имеют вторичную перетяжку кя обычно располагается вблизи дистального конца хромосомы и отделяет маленький участок спутник.
26680. Сцепление генов. Группы сцепления. Генетический анализ сцепления генов. Сцепление и перекрест в экспериментах Моргана с дрозофилой 12.78 KB
  Генетический анализ сцепления генов. Число хромосом у разных видов невелико по сравнению с числом генов. У дрозофилы более тысячи генов на 4 пары хромосом.
26681. Транскрипция – синтез РНК 14.63 KB
  Транскрипция синтез всех типов РНК 1 этап экспрессии генов. РНКполимеразы: Транскрипцию осуществлт фермент РНКполимераза особть фия: не требует праймера начинает работать с 1 нуклда работает в направлении 5→3 У прокариот РНКполимза E δ70 имеет большое колво субц 2α взаимодт с промотором; 2β актив. РНКполимза сочетт в себе полимеразную и хеликазю активть.
26682. Трансляция 16.84 KB
  Трансляция - реализация ген.программы клеток,происходит перевод ген.информации,закодированной в структуре НК,в аминокислотную последовательность белков. Это перевод четырехбуквенного(по числу постоянно встречающихся в ДНК и РНК нуклеотидов)