10045

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

Доклад

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

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

Русский

2013-03-20

46 KB

24 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

56318. Програми роботи з таблицями 78.5 KB
  Ми завершуємо ознайомлення з табличними величинами та програмами роботи з таблицями. Ви вмієте описувати масиви, вводити і виводити елементи масивів, складати програми опрацювання табличних величин. Але треба бути уважним і добре розуміти, що робиш і для чого.
56319. ЗАГАЛЬНІ ПОЛОЖЕННЯ НАПИСАННЯ ТЕКСТУ НАУКОВОЇ РОБОТИ ТА ЙОГО ОФОРМЛЕННЯ 24.36 KB
  Які існують прийоми осмислення тексту (і виділення інформаційно-смислових блоків)? Психологи називають три такі прийоми: виділення смислових опорних пунктів (або ключових слів), антиципація та реціпація
56320. ОСОБЛИВОСТІ МЕТОДИЧНОГО ЗАБЕЗПЕЧЕННЯ УЧБОВИХ ТА УЧБОВО-ДОСЛІДНИЦЬКИХ РОБІТ НА ПРИКЛАДІ УЧБОВОГО РЕФЕРАТУ, КОНТРОЛЬНОЇ Й КУРСОВОЇ РОБОТИ 18.36 KB
  Реферат (від латинського refezo – доповідаю, повідомляю) – це короткий виклад змісту документа або його частини, що включає основні фактичні відомості та висновки, необхідні для початкового ознайомлення з документом і доцільності звернення до нього.
56321. ОСОБЛИВОСТІ МЕТОДИЧНОГО ЗАБЕЗПЕЧЕННЯ УЧБОВИХ ТА УЧБОВО-ДОСЛІДНИЦЬКИХ РОБІТ НА ПРИКЛАДІ ДИПЛОМНОЇ (ВИПУСКНОЇ) РОБОТИ 17.12 KB
  Дипломна робота – це вид навчально-дослідницької діяльності, орієнтованої на розвиток вміння самостійно виконувати науковий аналіз питань, пов'язаних із специфікою освоюваної професії. Дипломна робота є заключним періодом навчання у вищій школі, так як вона виконується на випускному курсі під керівництвом наукового керівника.
56322. Нацистский «новый порядок» в Европе 110 KB
  Движение Сопротивления в Европе Цели движения Сопротивления: Движение Сопротивления - это освободительное движение в оккупированных странах Формы движения Сопротивления против внешнего и внутреннего фашизма и установленного фашистами порядка.
56323. ЗАГАЛЬНІ ПОЛОЖЕННЯ ЛОГІЧНИХ ДОВОДІВ (АРГУМЕНТАЦІЙ) 20.3 KB
  Наукове знання, як уже відомо, це результат наукового дослідження, перевірений суспільно-історичною практикою і не суперечить логіці. Значить, в будь-якому дослідженні, крім чуттєвого пізнання, використовується абстрактне мислення чи логічне пізнання.