Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
12277 = (31 - 2г)(399 + 20г) + (-132 + 178г), 399 + 2Oi = (-1 - t)(-132 + 178t) + (89 + 66t), -132 + 178t = (2г)(89 + 66г).
Таким образом, НОД есть 89 + 66І, т. е. 12277 = 892 + 662.
а) Воспользовавшись равенством 196 + 1 = 2- 132 • 181 • 769 и алгоритмом Евклида для гауссовых чисел, представить 769 в виде суммы двух квадратов.
б) Аналогично представить простое число 3877 в виде суммы двух квадратов, зная, что 3877 делит 156 + 1.
в) Зная, что простое число 38737 делит 236 + 1, представить 38737 в виде суммы двух квадратов.
§ 3. Сравнения
Основные свойства. Пусть даны три целых числа a, b и то; говорят, что а сравнимо с b по модулю то, если разность а — b делится на то. Записывают это так: a = b (mod то). Число то называется модулем сравнения. Из определения легко выводятся следующие свойства:
1. (i) a = a (mod то); (H) a = b (mod то) тогда и только тогда, когда b = a (mod то); (Hi) если a = b (mod то) и b = с (mod то), то а = с (mod то). Для фиксированного то свойства (i)-(iii) означают, что сравнимость по модулю то есть отношение эквивалентности.
2. Для фиксированного то каждый класс эквивалентности по этому отношению обладает в точности одним представителем в множестве чисел от 0 до то — 1. (Другими словами, любое целое число сравнимо по модулю то ровно с одним целым числом в промежутке от 0 до то — 1). Множество классов эквивалентности (они называются классами вычетов) будет обозначаться Z/mZ. Любое множество представителей (по одному от каждого класса — прим. перев.) называется полной системой вычетов по модулю то.
§ 3. СРАВНЕНИЯ
21
3. Если а = Ь (mod тп) и с = d (mod тп), то а ± с = b ± d (mod тп) и ас = bd (mod m). Другими словами, сравнения (по одному и тому же модулю) можно складывать, вычитать и перемножать. Таким образом, множество Ъ/тпЪ является коммутативным кольцом, т.е. классы вычетов можно складывать, вычитать и перемножать (причем результат не зависит от того, какие представители классов эквивалентности используются), и эти операции удовлетворяют обычным аксиомам ассоциативности, коммутативности, существования противоположного элемента и т. д.
4. Если a = b (mod т), то a = b (mod d) для любого делителя d\m.
5. Если a = b (mod т), a = b (mod п) и если тип взаимно просты, то a = b (mod тп). (См. пятое свойство делимости в § I. 2.)
Предложение 1.3.1. Обратимыми по умножению являются те элементы из Z/mZ, представители которых взаимно просты с т, т. е. числа а, для которых существует такое Ь, что ab = 1 (mod т), — это те и только те числа а, для которых НОД (а, т) = 1. Кроме того, если НОД (а,т) = 1, то обратный элемент b может быть найден за 0(\og т) двоичных операций.
Доказательство. Если бы d = НОД (а, т) был больше 1, то ни для какого b сравнение ab = 1 (mod т) не могло бы выполняться, так как в противном случае d делил бы ab — 1 и, следовательно, d\\. Обратно, если НОД (а, т) = 1, то согласно свойству 2 можно считать, что а < т. Тогда в соответствии с предложением 1.2.2 существуют целые числа и и v, которые можно найти за О (log т) двоичных операций и для которых аи -f- vm = 1. Полагая b = и, получаем, что m|l — аи = 1 — ab, что и требовалось.
Замечание. Если НОД (а,т) = 1, то под отрицательной степенью а п (mod п) подразумевают п-ю степень обратного класса вычетов, т.е. класс вычетов, содержащий п-ю степень любого целого числа b такого, что ab = 1 (mod т).
Пример 1. Найти 160 1 (mod 841), т.е. элемент, обратный к 160 по модулю 841.
Решение. Воспользовавшись результатом упражнения 6 с) из предыдущего раздела, получим ответ 205.
Следствие 1. Если р — простое число, то каждый ненулевой класс вычетов по модулю р имеет обратный, который может быть найден за O(log3 р) двоичных операций. Кольцо Ъ/рЪ является полем. Мы часто будем обозначать это поле Fp и называть полем из р элементов.
Следствие 2. Пусть требуется решить линейное сравнение ах = b (mod m); не теряя общности, можно считать, что 0 ^
22
гл. 1. элементарная теория чисел
a, b < т. Тогда если НОД (а,т) = 1, то сравнение имеет решение Xq, которое можно найти за O(log т) двоичных операций, и любое решение имеет вид х = X0 + тп, где п — некоторое целое число. Если же НОД (a, m) = d, то сравнение имеет решение тогда и только тогда, когда d\b, и в этом случае данное сравнение эквивалентно (в смысле совпадения множества решений) сравнению ах = b' (mod т'), где a' = a/d, b' = b/d, т = m/d.
Первое следствие есть просто частный случай предложения 1.3. I. Второе следствие легко вывести из предложения 1.3. 1 и определений. Так же, как при решении аналогичных линейных уравнений с вещественными коэффициентами, для решения линейных уравнений в Z/mZ умножают обе части на элемент, мультипликативно обратный коэффициенту при неизвестном.
Вообще, при вычислениях по модулю т аналогом понятия «ненулевой» является «взаимно простой с т». Выше было показано, что так же, как уравнения, сравнения можно складывать, вычитать и умножать (см. свойство 3 для сравнений). Их можно также делить, если «знаменатель» взаимно прост с т.
