Тест Ферма на простоту


Вход: число n – для проверки на простоту, t – параметр надежности.

1. Повторяем t раз:

а) Случайно выбираем a [2, n-2]

б) Если an–1 1 (mod n) «n – составное». Выход.

2. «n – простое с вероятностью 1–εt »

 

Этот тест может принять составное число за простое, но не наоборот.

Вероятность ошибки есть εt, где ε

В случае составного числа n, имеющего только большие делители, ε , то есть существуют числа, для которых вероятность ошибки при проверке их на простоту тестом Ферма близка к 1.

Для теста Ферма существуют так называемые числа Кармайкла – такие составные числа, что a: (a,n) = 1 an1 ≡ 1(mod n). То есть числа Кармайкла – это такие составные числа, которые всегда принимаются тестом Ферма за простые, несмотря на то, как велико число t – параметр надежности теста.

Теорема Кармайкла

n – число Кармайкла 1) n свободно от квадратов (т.е. n = p1p2∙…∙pk);

2) (pi – 1)\(n – 1), i = 1,…,k ;

3) k .

Наименьшее известное число Кармайкла n=561 = 3∙11·17

 

3.7. Применение теоремы Эйлера в RSA:

 

Если известно разложение числа на простые сомножители a = p1 p2 pn , то легко вычислить функцию Эйлера φ(a).

Отсюда вывод: сложность вычисления функции Эйлера не выше сложности задачи факторизации .

Покажем, что в случае n=pq (p,q – простые числа, p q) задачи нахождения функции Эйлера и факторизации эквивалентны. (то есть в случае, когда n – модуль RSA).

Учтем, что φ(n) = (p – 1)(q – 1). Тогда имеем систему

.

Зная n и φ(n), находим p и q из системы, приведенной выше, следующим образом:

Первое уравнение системы является квадратным уравнением относительно q,

q = , где Dq = [n– φ(n)+1]2 – 4n.

Подставляя полученное q во второе уравнение системы, находим p.

Видим, что при нахождении чисел p, q по известным n, φ(n) применяются только «дешевые» в смысле времени операции – сложение, деление на 2. Только при вычислении дискриминанта приходится применять возведение в степень, а при вычислении q – извлечение квадратного корня. Однако эти операции производятся однократно, поэтому временные затраты не столь существенны.

Итак, для модуля RSA задачи нахождения функции Эйлера и факторизации равносложны.

 

Формулировка теоремы Эйлера для RSA:

n = pq; p≠q; p, q – простые числа a выполняется akφ(n)+1a (mod n).

(на самом деле n может быть просто свободно от квадратов, то есть произведением произвольного количества различных простых чисел)

Доказательство:

Возможны два случая:

1) (a, n) = 1 по теореме Эйлера aφ(n) ≡ 1 (mod n)

akφ(n)+1 = 1k aa (mod n).

2) (a, n) ≠ 1, n не делит a в силу основного свойства простых чисел, либо p\ a, либо q \ a.

Не нарушая общности, предположим, что p\a, q не делит a.

Тогда по теореме Ферма, akφ(n)+1a(mod p),

qq–1≡1 (mod q) akφ(n)+1≡1k(p–1)·aa (mod q).

Итак, akφ(n)+1a (mod p), akφ(n)+1a (mod q). Отсюда по св-ву сравнений №12, akφ(n)+1a(mod НОК(p,q)). В силу простоты p и q, НОК(p,q)=pq=n, значит

akφ(n)+1a (mod n).

3) n\a a≡0(mod n) akφ(n)+1≡0≡a(mod n).

Примечание:

Если вместо φ(n) в теореме Эйлера для RSA взять НОК(p–1, q–1), теорема все равно будет верна.

 

Применение теоремы Эйлера в RSA:

Напомним, что криптосистема RSA является системой с открытым ключом. В качестве параметров системы выбираются различные большие простые числа p и q, вычисляется n=pq, φ(n)=(p–1)(q–1), выбирается число e: 2<e<n, (e, φ(n))=1 и вычисляется d=e-1(mod φ(n)). В качестве открытого ключа берется пара (n, e), в качестве закрытого, хранимого в секрете, четверка (p, q, φ(n), d).

Для того, чтобы зашифровать открытый текст x, абонент, пользуясь открытым ключом, вычисляет зашифрованный текст y по следующей формуле:

y = xe mod n.

Для того, чтобы осуществить расшифрование, владелец секретного ключа вычисляет

x = yd mod n.

В результате такого расшифрования действительно получится открытый текст, поскольку yd mod n=xed mod n=xed mod φ(n)mod n =x1 mod n=x.

Без знания простых сомножителей p и q сложно вычислить значение функции Эйлера φ(n), а значит, и степень d, в которую следует возводить зашифрованный текст, чтобы получить открытый.

Более того, знание простых сомножителей p и q может значительно облегчить процедуру возведения шифрованного текста y в степень d. Действительно, пользуясь теоремой Эйлера для RSA, можем понизить степень d. Разделим d на φ(n) с остатком:

d=kφ(n)+r

x=yd mod n= ykφ(n)+r mod n= yr mod n.

Еще более можно понизить степень, используя НОК(p–1,q–1)= вместо φ(n).

Пример:

n=19∙23=, φ(n)=18∙22=396, d=439.

НОК(18,22)=18∙22/2=198.

d mod φ(n)=43. d mod НОК(p–1,q–1)=43.

Число d=439 в двоичном представлении есть 110110111. Поэтому возведение в степень d c применением дихтономического алгоритма (см. гл.2) требует 8 возведений в квадрат и 6 умножений чисел.

Число 43 в двоичном представлении есть 101011. Возведение в степень 43 требует 5 возведений в квадрат и 3 умножения чисел. Кроме того, для вычисления φ(n) требуется 1 операция умножения.

Таким образом, для данного примера экономия времени составляет 2 сложные операции.

 

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




Дата добавления: 2018-11-26; просмотров: 891;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.014 сек.