Главная » Просмотр файлов » А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии

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

Файл №1127102 А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии) 9 страницаА.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102) страница 92019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

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

n, m>0, s=1.

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

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

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

Ш.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. Решение квадратичных сравнений по простому модулю.

Пусть дано сравнение x2a(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, получим

a2k+1≡1(mod p)

a2k+2a(mod p)

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

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

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

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

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

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

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

a2k+1≡—1(mod p)

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

24k+2a2k+1≡1(mod p)

24k+2a2k+2a(mod p)

x≡±22k+1ak+1(mod p)

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

x≡±ak+1(mod p).

x≡±22k+1ak+1(mod p)

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

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

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

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

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

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

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

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

N4k+2a2k+1≡1(mod p)

N4k+2a2k+2a(mod p)

x≡±N2k+1ak+1(mod p).

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

N4k+2a2k+1≡-1(mod p)

N12k+6a2k+1≡1(mod p)

N12k+6a2k+2a(mod p)

x≡±N6k+3ak+1(mod p)

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

x≡±ak+1(mod p)

x≡±N2k+1ak+1(mod p)

x≡±N4k+2ak+1(mod p)

x≡±N6k+3ak+1(mod p)

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

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

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

Пример:

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

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

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

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

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

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

.

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

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

1) x≡±8(mod 17) 5) x≡±348(mod p)

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

3) x≡±328(mod 17) 7) x≡±368(mod p)

4) x≡±338(mod 17) 8) x≡±378(mod p)

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

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

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

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

4) x≡±338≡±216≡±12(mod 17). Тогда x2≡144≡8(mod 17).

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

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

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

Пример:

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

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

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

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

x2≡1(mod 5).

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

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

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

x2≡86(mod 25)

x2≡11(mod 25)

(1+5t1)2≡11(mod 25)

1+10 t1+25 t12≡11(mod 25)

10 t1≡10(mod 25)

2 t1≡2(mod 5)

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

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

x2≡86(mod 125)

(6+25t2)2≡86(mod 125)

36+12·25t2+625t22≡86(mod 125)

12·25t2≡50(mod 125)

12t2≡2(mod 5)

2t2≡2(mod 5)

t2≡1(mod 5), или t2=1+5t3.

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

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

Рассмотрим теперь сравнение вида x2a(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), и таких решений будет четыре. Сравнение x2a(mod 2α) при α≥3 решается так же, как сравнения вида x2a(mod pα), только в качестве начального решения выступают решения по модулю 8: x≡±1(mod 8) и x≡±3(mod 8). Их следует подставить в сравнение по модулю 16, затем по модулю 32 и т. д. вплоть до модуля 2α.

Пример:

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

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

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

x2≡33(mod 16)

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

Тип файла
Документ
Размер
2,98 Mb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6430
Авторов
на СтудИзбе
306
Средний доход
с одного платного файла
Обучение Подробнее