Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Предложение 1.3.4. Пусть известно, что п есть произведение двух простых чисел. Тогда, зная эти числа р и q, можно найти ip(n) и обратно, зная п и <р(п), можно найти р и q. Точнее, <р(п) можно вычислить по р и q за O(logra) двоичных операций, а числа р и q можно вычислить по п и <р(п) за 0(log3 п) двоичных операций.
Доказательство. Утверждение очевидно, если п четно, так как в этом случае р = 2, q = n/2 и f(n) — n/2 — 1; поэтому предположим, что п нечетно. В силу мультипликативности функции (/P для п = pq получаем <р(п) = (р — l)(q — 1) = п + 1 — (р + q). Таким образом, значение ip(n) может быть получено из чисел р и q при помощи одного сложения и одного вычитания. Обратно, предположим, что известны п и </?(п), и надо найти р и q. Для неизвестных величин р и q известны их произведение п и сумма p + q^n + l — ц>(п).
§ 3. СРАВНЕНИЯ
25
Обозначим последнее выражение через 2b (р + q — число четное). Но два числа, произведение которых равно п, а сумма 26, должны быть корнями квадратного уравнения z — 2b z + п = 0. Итак, р и q равны b ± \/о—п. Наибольшее время при вычислении занимает процедура извлечения квадратного корня: в соответствии с упражнением 16 из § 1.1 на нее потребуется O(log3 п) двоичных операций. Предложение доказано.
Перейдем к обобщению малой теоремы Ферма, принадлежащему Эйлеру.
Предложение 1.3. 5. Если НОД (а, т) = 1, то а^т' = 1 (mod т).
Доказательство. Сначала докажем это утверждение в случае, когда т есть степень простого числа: т = р°. Проведем индукцию по а. При q=i получается малая теорема Ферма (предложение I. 3.2). Пусть Q ) 2 и формула верна для (а — 1)-й степени р.
Тогда ар р = 1 + р b для некоторого целого Ь. Возводя обе части этого равенства в степень р и используя тот факт, что все биномиальные коэффициенты в выражении (1 + х)р, кроме первого и
а _ а — 1
последнего, делятся на р, получаем, что а на 1 больше суммы,
( Q \
каждое слагаемое которой делится на р°. Другими словами, а — 1 делится на ра. Итак, теорема доказана для степеней простых чисел.
Наконец, из мультипликативности функции ip следует, что если ра\\т, то а^171^ = 1 (mod ра) (достаточно возвести обе части сравнения а^р ^ = 1 (mod р°) в соответствующую степень). Поскольку это верно для любого р \\т и поскольку степени различных простых чисел взаимно просты, из свойства 5 сравнений следует, что а = 1 (mod т).
Следствие. Если НОД (а, т) = 1 и если п — наименьший нео-трицательный вычет п по модулю <р(т), mo a = a (mod т).
Это следствие доказывается так же, как следствие из предложения 1.3.2.
Замечание. Как видно из доказательства предложения I. 3. 5, существует и меньшая степень а, сравнимая с 1 по модулю т: наименьшее общее кратное показателей степеней, сравнимых с 1 по модулю ра для каждого pQ||m. Например, а =1 (mod 105) для а, взаимно простого с 105, потому что 12 кратно 3 — 1,5 — 1 и 7 — 1. Заметим, что <?>(105) = 48. А вот еще один пример.
тт od „1000000 / і __ч
Пример 3. Вычислить 2 (mod 77).
Решение. Так как 30 есть наименьшее общее кратное чисел <р(7) = 6 и <р(11) = 10, на основании приведенного выше замечания получим 230 = 1 (mod 77). Так как 1000000 = 30-33333+ 10, получим
26
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
„1000000 _ о10 00 / , _„n Jj
/ = Z = 26 (mod 77). Другой способ решения заключается в
том, чтобы вычислить 21000000 (mod 7) (так как 1000000 = 6-166666+4, то это 24 = 2), то же проделать для 21000000 (mod 11) (так как 1000000 делится на 11 — 1, это 1) а затем, используя китайскую теорему об остатках, в промежутке от 0 до 76 найти такое х, что х = 2 (mod 7) и X = 1 (mod 11).
Возведение вычетов в степень методом повторного возведения в квадрат. Основным действием, которое часто встречается в арифметике вычетов, является отыскание значения bn (mod т) (т. е. нахождение наименьшего неотрицательного вычета) в случае, когда тип очень велики. Существует способ, гораздо более эффективный, чем вычисление Ь последовательным умножением на Ь. В дальнейшем будем предполагать, что b < т и что, вычислив произведение, мы тут же приводим его по модулю т (т. е. заменяем произведение его наименьшим неотрицательным вычетом). Тогда в процессе вычислений никогда не возникнут числа, превосходящие т . Теперь опишем алгоритм.
Используем символ а для обозначения промежуточного результата умножения. В конце а примет значение наименьшего неотрицательного вычета величины bn (mod то). Вначале положим а = 1. Пусть Uq,... ,Tik-x — цифры двоичной записи числа п, т.е. п —
к— 1
По + 2nj + 4тг2 + ¦ • • + 2 n^-i. Каждое Uj равно 0 или 1. Если п0 = 1, заменим а на 6 (в противном случае оставим а = 1). Затем возведем Ь в квадрат и положим O1 = b (mod т) (т. е. bi есть наименьший нео-трицательный вычет b по модулю т). Если ti1 = 1, умножим а на Ьх (и приведем по модулю тп); в противном случае сохраним прежнее значение а. Затем возведем в квадрат Ь\ и положим b2 = ^1 (mod тп). Если ti2 = 1, умножаем а на 62, в противном случае сохраняем прежнее значение а. Продолжаем далее по тому же правилу. Таким образом,
