Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
12. а) хА + X2 + 1 = (х2)(х2 + 1) + 1, 1 = l(z4 + X2 + 1) - х2(х2 + 1). б) г4 -4z3 + 6г2 - 4х + 1 = (г - 3)(г3 - х2 + х - 1) + [2х2 - 2), г3 - х2 + х - 1 = (|г - j)(2x2 - 2) 4- (2х - 2), 2z2 - 2 = (z + 1)(2г - 2), так что НОД равен х - 1; z-1 = (-1*+ 1)/+(1^-* + !^.
13. НОД (/,/') = г2 — X — 1, кратные корни — это (1 ± л/Е)/2 («золотое сечение» и сопряженное с ним число).
14. а) 5 + 6г = 2г(3 - 2г) + 1,1 = 1(5 + 6г) - 2г'(3 - 2г). б) 8 - 19г = 2(7 - lli) + (-6 + Зг), 7 - Пг = (-2 + г)(-6 + Зі) + (-2 + г), -6 + Зі = 3(-2 + і), так что НОД равен -2 + г; -2 + г = (-3 + 2г)(7 - 11г) + (2 - г)(8 - 19І).
15. а) 122 + 252. б) 542 + ЗІ2, в) 1162 + 1592.
§1.3
1. а) X = 6 + In при произвольном целом п. б) Нет решений, в) То же самое, что в а), г) 219 + 256га. д) 36 + 100га. е) 636 + 676га.
2. 0, 1, 4, 9.
3. 3, В.
4. Разность между га = 10k~ldk-i + • ¦ • + lOdi + do и суммой цифр dk-\ + ¦ ¦ ¦ + di +do есть сумма слагаемых, кратных числам вида 10J — 1, которые делятся на 9.
5. Доказать, что это число делится на 2, на 3 и на 5.
6. Пусть эти две цифры есть X и у. Тогда 72, а следовательно, и 8, и 9 делят сумму 100Oz + 60 + 2/ Центов. Таким образом, 8|(60 + у), а это означает, что у = 4. Далее, 91(1000а; + 64), что сравнимо с х + 1 по модулю 9. Поэтому х = 8. Итак, каждая плитка стоит $ 1,12.
7. а) Например, предположим, что m = 2ра. Так как т\(х2 — 1) = (г + 1)(г —1), то произведение чисел X + 1 и X — 1 должно делиться на ра. Но так как р ^ 3, то р не может делить и 1 + 1, и 1-1 (которые отличаются всего на два), и значит, ра должно делить одно из этих чисел. Если ра\(х + 1), то это означает, что X = — 1 (mod ра); если ра\(х — 1), то х = 1 (mod pa). Наконец, так как 2|(г2 — 1), то X должно быть нечетным, т.е. г = 1 = —1 (mod 2). Итак, по свойству 5 для сравнений либо X = I (mod 2pa), либо х = —1 (mod 2pa). б) Во-первых, если m ^ 8 есть степень двойки, то легко показать, что х = m/2 + 1 приводит к противоречию с частью а). Затем предположим, что m не является степенью простого числа (или удвоенной степенью простого числа) и что ра || т. Положим т' = т/ра. Воспользуемся китайской теоремой об остатках, чтобы найти такое х, которое было бы сравнимо с 1 по модулю ра и сравнимо с —1 по модулю т1. Показать, что это противоречит пункту а).
8. Разобьем все числа от 1 до р — 1 на пары взаимно обратных по умножению. На основании упражнения 7а) лишь 1 и —1 совпадают со своими обратными.
230
ОТВЕТЫ К УПРАЖНЕНИЯМ
Таким образом, когда эти р — 1 чисел перемножаются, каждая пара дает в произведении единицу и остаются еще 1 и —1.
9. Разумеется, 4 обладает нужными свойствами, но не является трехзначным числом. В силу последнего утверждения китайской теоремы об остатках любое другое число, имеющее нужные остатки, должно отличаться от 4 на число, кратное 7¦9¦1I = 693. Единственное такое трехзначное число — это 4 + 693 = 697.
10. Можно применить китайскую теорему об остатках к сравнениям х = 1 (mod 11), X ее 2 (mod 12), х = 3 (mod 13). Другой способ: можно заметить, что —10 дает нужные остатки, и затем, рассуждая, как в упражнении 9, получить -10 -4- 11 12 13 = 1706.
11. а) 1973. б) 63841. в) 58837.
12. Частное дает остатки 5, 1, 4 при делении на 9, 10, 11, и, следовательно (по китайской теореме об остатках), имеет вид 851 + 990т. Соответственно, делитель имеет вид 817 + 990га. Так как делитель трехзначный, то п = 0. Так как произведение шестизначное, то и m = 0. Ответ: 851.
13. Больше всего времени при применении китайской теоремы об остатках занимают: 1) вычисление М; 2) вычисление Mi = М/тгц для каждого из г различных модулей; 3) отыскание обратного для M1- по модулю т,- при каждом г; 4) умножение UiMiNi в формуле для х при каждом г; 5) деление полученного х на M для получения наименьшего неотрицательного значения. Для числа двоичных цифр в записи чисел m;, a,-, /Y1- имеем оценку O(logB), а для числа двоичных цифр в записи чисел M и М; имеем оценку 0(r log В). Это дает оценку 0(r2 log2 В) для числа двоичных операций при выполнении 1)-2), 4)-5). В 3) необходимо выполнить 0(r2 log2 В) двоичных операций для приведения каждого M1- по модулю соответствующего т,- перед вычислением обратных и затем 0(r log3 В) двоичных операций для нахождения всех г обратных по алгоритму Евклида. Это дает в итоге оценку 0(т(т + log S)log2 В). Который из двух членов этой оценки (г2 log2 В или г log3 В) является главным, зависит от соотношения величин г и log В (т.е. от числа уравнений и числа двоичных разрядов в модулях).
14. 381+2 + 23 + 26 = 38 • 2 • 16 • 63 ее 79 (mod 103).
15. Если использовать оценку 0(к2) для числа операций при одном умножении А:-значных двоичных чисел (как уже делалось), то никакого вьіиггльщха в оценке мы не получим. Действительно, самое последнее умножение требует времени 0((ralogi)2), что совпадает с оценкой для умножения b на себя п раз. Трудность состоит в том, что, в отличие от вычислений в кольце вычетов, в методе повторного возведения в квадрат мы подходим к концу, оперируя с парами очень больших чисел, что сводит на нет выигрыш от того, что количество умножений значительно меньше. Однако если бы мы воспользовались более рациональным способом умножения двух fc-значных двоичных чисел, например, алгоритмом, требующим лишь 0(к log к log log к) двоичных операций, это дало бы выигрыш во времени.
