Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 91

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 85 86 87 88 89 90 < 91 > 92 93 94 95 96 97 .. 311 >> Следующая

что ("р2^ = ("?) 1- Следовательно, —у Е QRn-
242
Часть II. Математические основы
3. Прежде всего, из теоремы 6.17.2 следует, что число х действительно имеет четыре квадратных корня. Обозначим их через и, —и(= п — и), v и —v. Далее, из условия и2 = v2{modn) следует, что {и + v)(u — v) = O(modp), т.е. и = ±w(modp). Аналогично и= ±v(modq). Однако по теореме 6.17.1 иф. ± w(modn), следовательно, возможны только два варианта:
и = w(modp) и и = —w(mod q),
или
и = —v(mod р) и и = v(mod q).
Отсюда, с учетом утверждения 1, следует, что (^) = — (^). Итак, если (?) = 1, то (?) = -1, а если (^) = -1, то (ь) = 1. Не ограничивая общности, можно утверждать, что четыре разных характери-зации символа Лежандра 3.1-3.4 следуют из мультипликативного свойства символа Лежандра-Якоби и утверждения 1.
4. Из утверждения 3 следует, что для любого у е QR„ существует единственный элемент х ? QR„, удовлетворяющий условию f(x) = у. Значит, f(x) представляет собой взаимно-оуднозначное отображение "на", т.е. перестановку над множеством QRn.
5. Из утверждения 3 следует, что квадратным корнем, символ Якоби которого равен единице, является число и или п — и. Поскольку число п — нечетное, только один из этих корней может быть меньше п/2. (Следовательно, только один квадратный корень, символ Якоби которого равен —1, может быть меньше п/2, а два остальных — больше п/2, причем их символы Якоби имеют противоположный знак.)
6. Легко проверить, что множество QR„ образует группу относительно умножения по модулю п, причем ее единицей является число 1. Из утверждения 3 следует, что четыре разных квадратных корня единицы имеют четыре! разных характеризации символа Лежандра 3.1-3.4. Следовательно, четыре множества QR„, (—l)QR„,?QRn и (—?)QR„ являются попарно непересе-| кающимися. Эти четыре множества образуют группу Z*, поскольку по тео! реме 6.15 #QR„ = ^. о
6.8 Резюме
В главе рассмотрены следующие темы теории чисел.
• Линейная сравнимость.
• Китайская теорема об остатках (с алгоритмом).
Глава 6. Теория чисел
243
• Теоремы Лагранжа, Эйлера и Ферма.
• Квадратичные вычеты и символы Лежандра-Якоби (с алгоритмом).
• Квадратные корни по целочисленному модулю и их связь с разложением числа на множители (с алгоритмом вычисления квадратного корня).
• Целые числа Блюма и их свойства.
Кроме того, изучено несколько важных алгоритмов (применение китайской теоремы об остатках, вычисление символа Якоби, вычисление квадратного корня), изложены их рабочие принципы и приведены оценки их временной сложности. Эти алгоритмы имеют не только теоретическое, но и практическое значение: они часто используются в криптографии с открытым ключом и криптографических протоколах.
Факты и алгоритмы, изложенные в этой главе, будут часто упоминаться в остальной части книга.
Упражнения
6.1. Пусть тип — положительные целые числа, удовлетворяющие условию т | п. Докажите, что операция "(modm)" разбивает группу Ъп на п/т классов эквивалентности, состоящих из т элементов каждый.
6.2. При тех же предположениях, что и в предыдущей задаче, докажите, что Z,n/mZn = Ът.
6.3. Используя китайскую теорему об остатках (алгоритм 6.1), найдите элемент группы Z35, образом которого при изоморфизме, определенном в теореме 6.8, является пара (2,3) е Z5 х Zj. Докажите, что этот элемент имеет максимальный порядок.
6.4. Применяя метод, описанный в примере 6.2, найдите три остальных квадратных корня числа 29 в группе Щ^. Вычислите четыре квадратных корня единицы в группе Щ5.
Подсказка: 29(mod5) = 4, причем число 4 имеет квадратные корни 2 и 3 (= —2(mod5)). Кроме того, 29(mod7) = 1, причем число 1 имеет квадратные корни 1 и 6 (= —l(mod7)). Четыре квадратных корня числа 29 по модулю 35 изоморфно отображаются в пары (2,1), (2,6), (3,1) и (3,6) в пространстве Z5 х Zj.
6.5. Найдите нечетное составное число п, которое не делилось бы на квадрат простого числа, однако удовлетворяло бы условию gcd(n, ф{п)) > 1.
6.6. Пусть т | п. Докажите, что для любого числа выполняется условие ordm(a;) | ord„(a;).
244
Часть II. Математические основы
6.7. Пусть тг = pq, причем числа р и g — простые. Поскольку р — 1 | ф(п), в группе Z* существуют элементы, порядок которых делится на р — 1. (Аналогично в группе 2? существуют элементы, порядок которых делится на g — 1.) Докажите, что для любого числа д 6 Z* из условий ordn(^) | р— 1 и ordn((?) \q — l следует, что gcd(<? — 1, п) = q. (Аналогично для любого элемента h 6 Z* из условий ordn(h) | д — 1 и ordn(h) \р — 1 следует, что gcd(ft — 1, п) = р.)
6.8. Пусть п = рд, причем числа р и д — простые. Докажите, что для любого элемента ^eZ* выполняется условие gp+q=gn+l(mod п). Покажите, что если \р\ « |д|, то верхней оценкой сложности разложения числа п на множители является число тг1/4.
Подсказка: найдите число р + q из условия gn+x{modn), используя Л-алго-ритм Полларда; затем разложите число тг на множители с помощью чисел р + q и pq.
6.9. Пусть р — простое число. Докажите, что порождающий элемент группы Ж* должен быть квадратичным невычетом. Аналогично, допустим, что п — нечетное составное число. Докажите, что элементы группы Z*, имеющие максимальный порядок, должны быть квадратичными невычетами.
Предыдущая << 1 .. 85 86 87 88 89 90 < 91 > 92 93 94 95 96 97 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed