Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
9. а) З2046 = 1013 (mod 2047), поэтому (1) не выполняется при 4 = 3. б) Каждое такое составное число будет псевдопростым по основанию 2. Действительно, пусть п = 22 +1 есть число Ферма. Тогда 22 = — 1 (mod п). Поэтому 2"-1 = 1 (mod п) (в этом можно убедиться повторным возведением в квадрат). Для п = 2Р — 1 имеем п — 1 = 2(2P_1 — 1) = 0 (mod р), и поэтому из 2Р = п + 1 = 1 (mod п) следует, что 2"-1 = 1 (mod п). Тест (2) при 4 = 2 также не будет работать, так как обе части будут равны 1, даже если п — составное. Тест (3) при 6 = 2 также не работает для числа Ферма, поскольку 22 = —1 (mod п); для числа Мерсенна это следует из предложения V. 1.5.
10. Раскрывая круглые скобки, показать, что п — 1 делится на 36т и, следовательно, на 6т, 12т, 18т.
12. Метод для решения пп. а) и б) упражнения дается в п. в), а) 561 = 3 -11 • 17. б) 1105 = 5 • 13 • 17, 2465 = 5-17-29, 10585 = 5-29-73. в) Пусть р < q. Так как (q — l)\{rpq — 1) = rp — 1 (mod q — 1), должно быть rp — 1 = a(q — 1), 1 < а < г. Аналогично, (р — 1)|(го — 1), и потому (р — l)\a(rq — 1) = r(aq) — а = г(а + гр — 1) — а = (г — 1)(а + г) (mod р — 1). Таким образом, при фиксированном г и любом фиксированном а, 2 ^ a ^ г — 1, для простого р существует лишь конечное число возможностей, а именно, р — 1 должно быть делителем (г — 1)(а + г). Если р выбрано, то q однозначно определяется условием rp — 1 = a(q — 1). Разумеется, не каждая пара аир дает число Кармайкла, так как, например, а может не быть делителем гр — 1.
13. Любое число Кармайкла, не перечисленное в упражнениях 12 а) и 12 6), должно быть произведением не менее чем трех различных простых чисел, каждое из которых не меньше 7.
14. n = 21, 4 = 8.
16. а) В упражнении 1 г) нужно проверять только те 4, для которых 4P_1 = ijy-r\~) = 1 (mod 2р - 1). Так как n - 1 = р - 1 (mod 2р - 2), то/Л$п=гУ2 = ft(p-i)/2 (mod р) и (mod 2р-1); следовательно, 4(п_1^2 = 4(р-1)/2 (mc!d п). Далее, (^¦) = ( 2;,-і )(р ) = (р) = 4^-1)/2 (mod р), следовательно, условие (2) эквивалентно б(?-1)/2 = (^) (mod 2р — 1). Оно выполняется в точности для половины всех 6, для которых 4P_1 = 1 (mod 2р — 1) (так как в (Z/(2p — I)Z)* такой элемент 4 должен быть такой степенью gJ образующего элемента д, что ^-j^j = 0 (mod 4), если (-) = 1, fc^ij = 2 (mod 4), если (-) = -1). б) n = р(2р-1), где р = 3 (mod 4)
р z р
(см. предложение V. 1. 5).
17. Найти п по модулю 72m: n = 36т2 + 36т + 1. Таким образом, "Г1 = 18т(т + 1) (mod 36т). Если т нечетно, отсюда следует, что всегда ft(n_1)/2 = 1 (mod п) (так как (р— 1)|36т для каждого р\п). Поэтому (2) выполняется тогда и только тогда, когда (^¦) = 1, т.е. в 50% случаев. Если m четно, то, по-прежнему, (,("-1)/2 = і (mod 6m -f 1) и (mod 18m 4- 1), в то время как 6("_1)/2 = 66га = (їіт+ї) (m°d 12m+ 1). В этом случае (2) выполнено тогда и только тогда, когда (12r^ + 1) = 1 (так что 4("-1)/2 = 1 (mod п)), а также (^) = 1, т.е. в 25% случаев.
18. a) O(log3nlogm). б) 0(log5 п).
ОТВЕТЫ К УПРАЖНЕНИЯМ
245
19. a) N — составное число, поскольку таковым является п (по следствию из предложения 1.4. 1); далее методом упражнения 9 убедиться, что 2^N~1^'2 = 22"-1-1 = 1 (mod N). Но так как N = -I (mod 8), то (-|-) = 1. Таким образом, N есть эйлерово псевдопростое; по предложению V. 1.5 оно также и сильно псевдопростое, б) Использовать тот же подход, что и в упражнении 7 в).
20. Если в (3) реализуется первая из возможностей, то, очевидно, (4*)' ее 1 (mod п). Теперь предположим, что 42 ' ее — 1 (mod п). Положить к = 2'j, где j нечетно. Если і > г, то (4*)' ее 1 (mod га); если і < г, то (4*)2Г '* = (62r')J ее (-1)-> = -1 (mod га).
21. а) Показать, что необходимые и достаточные условия на 4 — это (уу) = 1, (jrfy) = 1- Оба эти условия выполняются в 25% случаев, т.е. для 80 оснований в (Z/561Z)*. б) Так как 470 E= 1 (mod 3) и (mod 11), то 561 — сильно псевдопростое по основанию 4 в том и только том случае, когда б35 ее ±1 (mod 561), т.е. тогда и только тогда, когда либо 1) Ь ее 1 (mod 3), 4 ее 1 (mod 17), (уу-) = 1, либо 2) 4 ее —1 (mod 3), 4 E= — 1 (mod 17), (уу) = —1. Согласно китайской теореме об остатках существует 10 таких оснований (по 5 в случаях 1) и 2)). Помимо тривиальных ±1, это Ь = 50, 101, 103, 256, 305, 458, 460, 511.
22. Использовать упражнение 7 а) к §1.3, согласно которому квадратными корнями из единицы являются лишь ±1.
23. a) 82 ЕЕ 182 ее -1 (mod 65); 142 ЕЕ 1 (mod 65), но 141 её ±1 (mod 65). б) Случай, когда га — степень простого числа, рассматривается как следствие из предыдущего упражнения. Предположим поэтому, что га не есть степень простого числа. Во-первых, если р\п, р ее 3 (mod 4), то никакое целое число в четной степени не сравнимо с —1 по модулю п, так как —1 не есть квадратичный вычет по модулю р. Следовательно, в данном случае условие сильной псевдопростоты представимо в виде 4( ее ±1 (mod п). Это условие обладает, очевидно, свойством мультипликативности. Далее, предположим, что п =¦ р"1 ¦¦¦р?т, где pj ее 1 (mod 4), j = 1,2,..., г. Пусть ±а;- — два квадратных корня из — 1 по модулю pj3 (квадратный корень по модулю pj можно преобразовать в
