Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
на j-M шаге вычисляем bj = b\ (mod тп). Если nj — 1, т.е. если 2J входит в двоичное представление числа п, используем bj как множитель для вычисления нового значения а (и не делаем этого при rij = 0). Легко убедиться, что после (к - 1)-го шага получим а = 6™ (mod тп).
Сколько двоичных операций потребует алгоритм? На каждом шаге необходимо выполнить 1 или 2 умножения чисел, которые меньше тп . И потребуется выполнить к — 1 шагов. Так как на каждом шаге
2 2 2
требуется O(log (m )) = O(log тп) двоичных операций, то получаем следующую оценку.
Предложение 1.3.6. Time(6n mod m) — O((logn)(log2 m)).
Замечание. Если п очень велико, можно попробовать вое-
§ 3. СРАВНЕНИЯ
27
пользоваться следствием из предложения 1.3.5, заменив п его наименьшим неотрицательным вычетом по модулю <р(т). Но для этого нужно знать </?(т). Если <р(т) известно и НОД (b,m) = 1, то можно заменить п его наименьшим неотрицательным вычетом по модулю 1~р(т), и оценка в правой части предложения L 3. 6 примет вид O(log3 т + (logn) logm) (Слагаемое (logn) logm соответствует вычислению остатка от деления п на <f(m). — Прим. ред.)
Применяя еще раз мультипликативность функции Эйлера р(п), выведем формулу, которая будет использована в начале главы П. "Предложение 1.3.7. EdIn^(6O = п.
Доказательство. Обозначим через /(п) левую часть этого равенства, т.е. пусть /(п) — сумма значений tp(d) по всем делителям d числа п (включая 1 и га). Требуется доказать, что /(га) = га. Покажем сначала, что функция /(га) мультипликативна, т. е. f(mn) = /(m)/(n) при НОД (т,п) = 1. Заметим сначала, что любой делитель d числа тп может быть единственным образом представлен в виде произведения d\d2, где o1Im, d2\n. Так как НОД (di, d2) = 1, то <f(d) = (f(di)(f(d2) в силу мультипликативности функции (f. Мы получим все возможные делители d числа тп, взяв все возможные пары dx,d2, где dx\m, d2\n. Таким образом,/(mn) = Ed1 |m ?d2|n V7KM^) = (Ed1Im V(^i))(Ed2In ^(^2)) = fim)f(n)- Теперь для доказательства теоремы предположим, что п = Pi1P22 ¦ ¦ ¦Prг есть разложение п на простые множители. Так как / мультипликативна, то /(га) есть произведение чисел вида f(pa). Поэтому достаточно доказать предложение для ра, т.е. доказать, что f(p°) = р°¦ Но все делители числа ра имеют вид р3, где О ^ j ^ а, и поэтому f(pa) = Ej=o f(P3) = 1 + EjLi(P17 — Р3 1) = ра- Это доказывает теорему для чисел вида ра, а значит, и для всех га.
УПРАЖНЕНИЯ
1. Опишите все решения следующих сравнений:
а) Зх = 4 (mod 7); г) 27z = 25 (mod 256);
б) Зх = 4 (mod 12); д) 27z = 72 (mod 900);
в) 9x = 12 (mod 21); e) 103z = 612 (mod 676).
2. Какой цифрой может заканчиваться полный квадрат в шестнадцатиричной системе счисления (см. упражнение 7 к §1.1)?
3. Какой цифрой может заканчиваться произведение двух последовательных нечетных положительных чисел в двенадцатиричной системе счисления?
4. Доказать, что в десятичной системе счисления целое число тогда и только тогда делится на 3, когда сумма его цифр делится на 3, и что число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.
28
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
5. Доказать, что п5 — п всегда делится на 30.
6. Чтобы выложить плиткой пол размером 8 футов х 9 футов, вы купили 72 плитки по цене, которую не можете вспомнить. Общая сумма покупки, проставленная в вашем чеке, меньше $100, однако первая и последняя цифры неразборчивы. Запись выглядит так: $?0.6?. Сколько стоила одна плитка?
7. а) Пусть m есть либо степень ра простого числа р > 2, либо удвоенная степень простого нечетного числа. Доказать, что если х2 = 1 (mod m), то либо х = 1 (mod m), либо х = — 1 (mod m).
б) Доказать, что утверждение п. а) неверно, если т не представимо в виде ра или 2ра и т ф 4.
в) Доказать, что если т — нечетное число, которое делится на г различных простых чисел, то сравнение х2 = 1 (mod m) имеет 2Г различных решений между 0 и т.
8. Доказать теорему Вильсона, которая утверждает, что (р — 1)! = —1 (mod р) для любого простого р. Доказать, что (т — 1)! не сравнимо с —1 по модулю т, если т не является простым.
9. Найти трехзначное (в десятичной записи) целое число, которое дает остаток 4 при делении на 7, 9 и 11.
10. Найти наименьшее целое положительное число, которое при делении на 11 дает остаток 1, при делении на 12 — остаток 2, а при делении на 13 — остаток 3.
11. Найти наименьшее неотрицательное решение каждой из следующих систем сравнений:
X = 2 (mod 3) X = 12 (mod 31)
X = 3 (mod 5) X s 87 (mod 127) 19z = 103 (mod 900)
а) б) в)
X = 4 (mod 11) X ~ 91 (mod 255) 1Oe = 511 (mod 841)
X — 5 (mod 16)
12. Предположим, что трехзначное (в десятичной записи) положительное целое число, дающее остаток 7 при делении на 9 и 10 и остаток 3 при делении на 11, является делителем некоторого шестизначного натурального числа, которое при делении на 9, 10 и 11 дает, соответственно, остатки 8, 7 и 1. Найти частное.
13. В условиях ПреДЛОЖеНИЯ 1.3.3 предположим, что 0 Ctj < TUj < В для
