Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 112

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 106 107 108 109 110 111 < 112 > 113 114 115 116 117 118 .. 125 >> Следующая


17. во-первых, доказать, что элемент b' = -1) принадлежит Fpd,

показав, что он неподвижен относительно (Xі (т. е. возведя его в степень pd). далее убедиться, что он — образующий, так как степени (Ъ1)1, j = О, 1, ..., pd — 2, все различны. это следует из того, что первые рп — 1 степеней элемента 6 различны.

§И.2

1. множества вычетов: {1} для р — 3, {1,4} для р = 5, {1,2,4} для р = 7, {1, 3,4, 9, 10, 12} для р = 13, {1, 2, 4, 8, 9, 13, 15, 16} для р = 17, {1, 4, 5, 6, 7, 9, 11, 16, 17} для р = 19.

2. б) из части а) и предложений ii. 2. 2 и п. 2.4 следует, что (^) = 1 = 2(P-1)/2 (mod р). это означает, что ((р — 1)/2()-я степень 2 сравнима с —1 по модулю р для некоторого / ^ 2. так как 22* = —1 (mod р), можно показать, что НОД ((р — l)/2(,2fc) = 2*. отсюда сразу следует, что р ее 1 (mod 2fe + '). в) единственным простым числом, сравнимым с 1 по модулю 64 и меньшим, чем л/65537, является 193, однако оно не делит 65537.

3. НОД (84,1330) = 14.

4. использовать равенство (~) — ("у~)(р) и рассмотреть 4 возможных случая р= 1,3,5,7 (mod 8).

5- (т??) = (гЬКш) - -(1t)(W) = -Ш\Т) = "(-IK-1) = "I-

6. а) 14. б) 9. в) 9а.

7. а3 — а (см. доказательство предложения ii. 2. 4); 6, 60, 4080, 24, 210, 336.

8. примитивный р-й корень ? из единицы в F4 существует, так как q = 1 (mod р). далее, квадрат числа G = 5^у = і (р~)?; равен (~-)р (см. лемму в доказательстве предложения п. 2. 5).

9. a) ( —-) Y7j = \ (р )aJ! 6' 45i 3126, 906 (в последнем случае использовать равенство 1093 = (з7 — 1)/2). б) пусть g = JZy = I (p")2''- тогда наименьший положительный квадратный корень из {-—}-)р по модулю 2Р — 1 равен з, если р = 5 (mod 8), равен —д, если р = 3 (mod 8), равен р + д, если р = 7 (mod 8), и равен р — </), если р s 1 (mod 8). 7

1п / 1801 і _ /8191ч _ / 987 ч, _ / 3 ч/ 7 ч/ 47 ч _ /14/2.v1it- 1 1

1U- V8191-1 - Чв01^ ~ ~ ч 1801 ^ 1801 ^1 1801 — v3A7A47; — 1 " 1 '

(ava.) = -(2v2i = _1 61 f -Эв7_\ _ /1801) = (?_407 ч = / 1 )( 987 ) = (173ч =

V47 а 47; - V3A5;- и) V18011 V Э87; - V 9g7 ; v 1A407-' V 407;

(MI) = (JiL) = / из) = (Щ = (UL) = (2a) = -(jl) = -(IL) = -1

11. а) 1. б) 1. в) 1. г) 1. д) 1. е) 1. ж) -1.

12. a) (f) = (f)(3-) = (-1^-1)/2(-1)(3-1)(1.-1)/4(1) = (|); это равно 1

тогда и только тогда, когда р ее 1 (mod 3). б) ( 2p3_t ) = — (2 3~1 ) = —(3) = — 1-

13. последняя десятичная цифра должна быть 1 или 9.

14. любая степень вычета есть вычет, поэтому никакой невычет не может встретиться среди этих степеней, а это означает, что вычет не может быть образующим.

15. а) так как р — 1 есть степень 2, то порядок всякого элемента д есть степень 2. если д — невычет, то —1 = (?) ее д(г>-1)/2 (modp). поэтому порядок д не может

быть меньше р - 1. б) если к > 1 и р = 22* + 1, то р ее 2 (mod 5) (так как степень, в которую возводится 2, делится на 4). поэтому (^) = (|-) = (j) = —1 и б) следует из а), в) аналогично б): так как 2 возводится в степень, не делящуюся

ОТВЕТЫ К УПРАЖНЕНИЯМ

235

на 3, то р — 1 = 2 или 4 (mod 7), следовательно, р = 3 или 5 (mod 7). Поэтому (^) = (?¦) = —1, и в) следует из а).

16. а) Имеем: (a + bi)p + 1 = (ар + bpip)(a + 6г) = (о - Ы)(а + Ы) = а2 + б2. Утверждение. ?с/ш (а + 6г)т Є Fp, то (р + I)Im. Чтобы доказать это утверждение, положим d — НОД (т,р + 1). Используя те же аргументы, что и в доказательстве предложения 1.4. 2, видим, что (a + bi)d Є Fp. Однако, так как р+1 есть степень 2, то в случае d < р + 1 мы находим, что (а + 6г)(р+1)/2 — элемент Fp, квадрат которого есть a2 + б2. Но а2 + б2 есть невычет (см. упражнение 14), поэтому d = р + 1 и (р + 1)|ш. Пусть теперь п таково, что (а + 6г)" = 1. Тогда, по доказанному утверждению, п = (р + \)п'. Следовательно, (a2 +62)" = 1; так как а2 + б2 — образующий F*, то (р — 1)|га'. б) Достаточно показать, что 17 и 13 — образующие F31.

17. В обоих случаях получаем 0(log3p). Заметим, однако, что предложение И. 2. 2 применимо к ( —) лишь тогда, когда п — р есть простое число. В то же время метод из части а) применим при любом нечетном натуральном п. Заметим также, что время работы при а) может быть сокращено до 0(log2 р) методом, использованным в упражнении 11 к §1.2.

18. а) Показать, что число решений квадратичного сравнения равно числу решений сравнения х2 = D (mod р). Имеется одно решение, если D = 0, ни одного, если D — невычет, и 2, если D — вычет, б) 0, 0, 2, 1, 2. в) 2, 2, 1, 0, 0.

19. п = 3, р - 1 = 25 ¦ 65, г = 30233 = 203 (mod р) (мы вычисляем 30233 методом повторного возведения в квадрат, последовательно возводя в квадрат 5 раз и затем умножая результат на 302). Также методом повторного возведения в квадрат вычисляем 6 = я65 = 888 (mod р). Наконец, берем j = 22, т.е. V/3O~2 (mod р) = 64г = 1292 (mod р).

20. а) Использовать индукцию по а. Чтобы перейти от а — 1 к а, предположить, что x — такое (а — 1)-значное число в системе счисления с основанием р, что x2 = a .(mod pa_1). Чтобы определить последнюю цифру za-i Є {0,1,..., р — 1} искомого решения 1=2 + xa-\pa~l, записываем х2 = a + 6pa_1 для некоторого целого числа 6 и затем действуем по модулю ра: х2 = (х + хQ_ipa_1)2 = х2 +2гога_іра_1 = а + ра_1(6 + 2гоз;а-1). Таким образом, достаточно выбрать ia-i = —(2xo)~lb (mod р) (заметим, что 2xq обратимо по модулю р, так как р нечетно, а Ij = а (mod р), где а взаимно просто с р). б) Использовать китайскую теорему об остатках, чтобы найти х, который сравним по каждому модулю ра с квадратным корнем, найденным в части а).
Предыдущая << 1 .. 106 107 108 109 110 111 < 112 > 113 114 115 116 117 118 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed