А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Вход: n - числитель, m – знаменатель символа Якоби. m – нечетное число,

n, m>0, s=1.

Ш.1: Если (n,m)≠1, то s:=0. Идти на Выход.

Ш.2: n:=n mod m. Ш.3.

Ш.3: Представить n как n=2^kn₁ . k:=k mod 2, n:=n₁.

Ш.4: Если k=1, то если m mod 8 = 3 или m mod 8 = 5, то s:=—s .

Ш.5: Если n=1, то идти на Выход.

Ш.6: Если n=m—1, и m mod 4 = 1, то идти на Выход.

Если n=m—1, и m mod 4 = 3, то s:=—s. Идти на Выход.

Ш.7: n↔m. s:=s·(—1) . Идти на Ш.2.

Выход. s – символ Якоби.

Пример:

.

5.3. Тест на простоту Соловея-Штрассена.

Символ Якоби отличается от символа Лежандра тем, что в первом знаменатель – составное число, а во втором – простое. Алгоритм вычисления символа Якоби и символа Лежандра одинаков, но для символа Якоби не выполняется критерий Эйлера.

Пусть мы имеем нечетное число n, о котором неизвестно, простое оно или составное. Символ является символом Лежандра, если n – простое, и тогда для него выполняется критерий Эйлера, то есть .

Если же n – составное число, то символ является символом Якоби, и тогда вышеуказанное сравнение, возможно, не выполняется. (Мы говорим «возможно», так как для некоторых a и n, в силу случайного совпадения, сравнение может оказаться верным.)

Поэтому если найдется такое a (1 < a < n), что , то можно наверняка утверждать, что число n – составное. На этом факте основан тест Соловея-Штрассена.

Тест Соловея-Штрассена:

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

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

1.1 Случайно выбираем a:

1.2. Если “n – составное”. Выход.

1.3. Вычисляем ,

1.4. Если r ≠s “n –составное ”. Выход.

2. “n –простое с вероятностью 1— ε^t ”. Выход.

Как и тест Ферма, этот тест может принять составное число за простое, но не наоборот. Вероятность ошибки (то есть вероятность принять составное число за простое) составляет ε^t, где t – число итераций теста, параметр надежности, а < .

Как видим, оценка надежности теста Соловея–Штрассена гораздо лучше, чем для теста Ферма, даже в том случае, когда φ(n) ненамного меньше n.

5.4. Решение квадратичных сравнений по простому модулю.

Пусть дано сравнение x²≡a(mod p), p>2 – простое и .

Данное сравнение имеет 2 решения. Укажем, как найти эти решения.

Для p возможны следующие случаи:

p :

p≡3(mod 4) p≡1(mod 4)

p≡5(mod 8) p≡1(mod 8)

p≡9(mod 16) p≡1(mod 16)

И т. д.

а)Пусть p≡3(mod 4), т.е. p=4k+3.

По критерию Эйлера, . Подставляя сюда p, получим

a^2k+1≡1(mod p)

a^2k+2≡a(mod p)

Вернувшись сравнению, которое требуется решить, заметим, что x²≡a^2k+2(mod p), и тогда x≡±a^k+1(mod p) – искомое решение.

б) p≡5(mod 8), т.е. p=8k+5.

Найдем какой-нибудь квадратичный невычет по модулю p. Согласно св-ву 7 для символа Лежандра, таким невычетом в случае p=8k+5 будет являться «2». Тогда, согласо критерию Эйлера, 2^4k+2≡—1(mod p).

Так как a – квадратичный вычет по модулю p, то по критерию Эйлера, .

Тогда возможны два варианта: a^2k+1≡1(mod p) или a^2k+1≡—1(mod p).

В первом случае дальнейшие рассуждения проводим как в пункте а, и получаем x≡±a^k+1(mod p).

Рассмотрим подробнее второй случай. Имеем:

a^2k+1≡—1(mod p)

Для того, чтобы избавиться от знака (—) в правой части, домножим левую часть этого сравнения на 2^4k+2, а левую – на –1.

2^4k+2a^2k+1≡1(mod p)

2^4k+2a^2k+2≡a(mod p)

x≡±2^2k+1a^k+1(mod p)

Таким образом, имеются два кандидата на решение:

x≡±a^k+1(mod p).

x≡±2^2k+1a^k+1(mod p)

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

в) p≡9(mod 16), т.е. p=16k+9.

Найдем N – какой-нибудь квадратичный невычет по модулю p. Тогда по критерию Эйлера, .

С другой стороны, поскольку a – квадратичный вычет по модулю p, то по критерию Эйлера, .

Тогда возникают два случая: a^4k+2≡1(mod p) или a^4k+2≡-1(mod p).

Рассмотрим первый случай: a^4k+2≡1(mod p). Поскольку показатель степени в левой части сравнения – четный, то вновь возникают два варианта: a^2k+1≡1(mod p) или a^2k+1≡—1(mod p), первый из которых приводит, как ранее, к кандидату в решение x≡±a^k+1(mod p), а второй вариант, рассуждая как в пункте б, приведем к кандидату в решения x≡±N^4k+2a^k+1(mod p).

Рассмотрим второй случай: a^4k+2≡-1(mod p). Для того, чтобы избавиться от знака (—) в правой части сравнения, домножим правую часть на N^8k+4, а левую – на –1. Получим N^8k+4a^4k+2≡1(mod p). Поскольку показатели степеней в левой части получившегося сравнения четны, то отсюда возникают два варианта: N^4k+2a^2k+1≡1(mod p) или N^4k+2a^2k+1≡-1(mod p).

Рассмотрим первый из вариантов:

N^4k+2a^2k+1≡1(mod p)

N^4k+2a^2k+2≡a(mod p)

x≡±N^2k+1a^k+1(mod p).

Рассмотрим второй из вариантов:

N^4k+2a^2k+1≡-1(mod p)

N^12k+6a^2k+1≡1(mod p)

N^12k+6a^2k+2≡a(mod p)

x≡±N^6k+3a^k+1(mod p)

Итак, получили четыре пары – кандидата на решение:

x≡±a^k+1(mod p)

x≡±N^2k+1a^k+1(mod p)

x≡±N^4k+2a^k+1(mod p)

x≡±N^6k+3a^k+1(mod p)

Вычислив и подставив в исходное сравнение, выберем ту пару, которая удовлетворяет исходному сравнению.

Рассмотренным способом можно построить решение для любого простого модуля p. Если p=2^hk+2^h—1+1, то при решении сравнения возникнет 2^h—2 пар – кандидатов в решение, каждая из которых будет иметь вид x≡±N^z(2k+1)a^k+1(mod p), где .

Главная проблема здесь – отыскание квадратичного невычета N, но поскольку, как было доказано ранее, квадратичных вычетов и невычетов по простому модулю – одинаковое количество, то невычет обязательно найдется.

Пример:

Решить сравнение x²≡8(mod 17).

17 – простое число. Выясним, имеет ли данное сравнение решение:

. Сравнение имеет 2 решения. Отыщем их.

17=2·8+1=4·4+1=8·2+1=16·1+1=32·0+17=2⁵·0+17.

h=5, k=0. Имеется 2³=8 пар-кандидатов в решения.

Найдем какой-нибудь невычет по модулю 17:

.

Итак, N=3 – кв. невычет по модулю 17.

Имеются следующие кандидаты в решения сравнения:

1) x≡±8(mod 17) 5) x≡±3⁴8(mod p)

2) x≡±3·8(mod 17) 6) x≡±3⁵8(mod p)

3) x≡±3²8(mod 17) 7) x≡±3⁶8(mod p)

4) x≡±3³8(mod 17) 8) x≡±3⁷8(mod p)

Будем проверять каждую пару решений, пока не найдем верное решение.

1) x≡±8(mod 17). Тогда x²≡64≡13(mod 17).

2) x≡±3·8≡±24≡±7(mod 17). Тогда x²≡49≡15(mod 17).

3) x≡±3²8≡±72≡±4(mod 17). Тогда x²≡16(mod 17).

4) x≡±3³8≡±216≡±12(mod 17). Тогда x²≡144≡8(mod 17).

Ответ: x≡±12(mod 17), или x≡±5(mod 17).

5.5. Квадратичные сравнения по составному модулю.

Рассмотрим сравнение вида x²≡a(mod p^α), где p – простое нечетное число. Как было показано в п.4 §4, решение этого сравнения можно отыскать, решив сравнение x²≡a(mod p). Причем сравнение x²≡a(mod p^α) будет иметь два решения, если a является квадратичным вычетом по модулю p.

Пример:

Решить квадратичное сравнение x²≡86(mod 125).

125 = 5³, 5 – простое число. Проверим, является ли 86 квадратом по модулю 5.

. Исходное сравнение имеет 2 решения.

Найдем решение сравнения x²≡86(mod 5).

x²≡1(mod 5).

Это сравнение можно было бы решить способом, указанным в предыдущем пункте, но мы воспользуемся тем, что квадратный корень из 1 по любому модулю есть ±1, а сравнение имеет ровно два решения. Таким образом, решение сравнения по модулю 5 есть

x≡±1(mod 5) или, иначе, x=±(1+5t₁).

Подставим получившееся решение в сравнение по модулю 5²=25:

x²≡86(mod 25)

x²≡11(mod 25)

(1+5t₁)²≡11(mod 25)

1+10 t₁+25 t₁²≡11(mod 25)

10 t₁≡10(mod 25)

2 t₁≡2(mod 5)

t₁≡1(mod 5), или, что то же самое, t₁=1+5t₂.

Тогда решение сравнения по модулю 25 есть x=±(1+5(1+5t₂))=±(6+25t₂). Подставим получившееся решение в сравнение по модулю 5³=125:

x²≡86(mod 125)

(6+25t₂)²≡86(mod 125)

36+12·25t₂+625t₂²≡86(mod 125)

12·25t₂≡50(mod 125)

12t₂≡2(mod 5)

2t₂≡2(mod 5)

t₂≡1(mod 5), или t₂=1+5t₃.

Тогда решение сравнения по модулю 125 есть x=±(6+25(1+5t₃))=±(31+125t₃).

Ответ: x≡±31(mod 125).

Рассмотрим теперь сравнение вида x²≡a(mod 2^α). Такое сравнение не всегда имеет два решения. Для такого модуля возможны случаи:

1. α=1. Тогда сравнение имеет решение только тогда, когда a≡1(mod 2), и решением будет x≡1(mod 2) (одно решение).

2. α=2. Сравнение имеет решения только тогда, когда a≡1(mod 4), и решением будет x≡±1(mod 4) (два решения).

3. α≥3. Сравнение имеет решения только тогда, когда a≡1(mod 8), и таких решений будет четыре. Сравнение x²≡a(mod 2^α) при α≥3 решается так же, как сравнения вида x²≡a(mod p^α), только в качестве начального решения выступают решения по модулю 8: x≡±1(mod 8) и x≡±3(mod 8). Их следует подставить в сравнение по модулю 16, затем по модулю 32 и т. д. вплоть до модуля 2^α.

Пример:

Решить сравнение x²≡33(mod 64)

64=2⁶. Проверим, имеет ли исходное сравнение решения. 33≡1(mod 8), значит сравнение имеет 4 решения.

По модулю 8 эти решения будут: x≡±1(mod 8) и x≡±3(mod 8), что можно представить как x=±(1+4t₁). Подставим это выражение в сравнение по модулю 16

x²≡33(mod 16)

Характеристики

Список файлов книги