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

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

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 24 25 26 27 28 29 < 30 > 31 32 33 34 35 36 .. 125 >> Следующая


3 2 2 2 2

чательная оценка имеет вид О (log р+« log р) = O((logp-ba )log р). В худшем случае (если р— 1 лишь небольшим множителем отличается от степени 2) это составляет O(log4p), так кар а < log2 р = O(logp). Таким образом, если дан невычет п по модулю р, то можно извлечь квадратный корень по модулю р за полиномиальное время (ограниченное 4-й степенью числа бит в записи р).

3. В настоящее время не известны строгие (не использующие так называемую «гипотезу Римана») доказательства существования алгоритма, который находит за полиномиальное время невычет по модулю р. Однако, для любого є > 0 существует алгоритм, который за полиномиальное время находит невычет с вероятностью, большей 1-Е. А именно, случайно выбранное число п, 0 < п < р, с вероятностью 1/2 является невычетом, и это можно проверить за полиномиальное время (см. упражнение 17 ниже). Если мы проделаем это для более

58

ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ

чем log2(l/e) различных случайно выбранных п, то с вероятностью, большей, чем 1 — ?, по крайней мере, одно из них будет невычетом.

УПРАЖНЕНИЯ

1. Составить таблицу всех квадратичных вычетов и невычетов по модулю р для р = 3, 5, 7, 13, 17, 19.

2. Предположим, что р|22 +1, где к > 1.

а) Используя упражнение 4 §1.4 показать, что р = 1 (mod 2* + 1).

б) Используя предложение II. 2. 4, доказать, что р = 1 (mod 2^ + 2).

в) Используя часть б), показать, что 216 + 1 — простое число.

3. Сколько корней степени 84 из единицы содержится в поле из II3 элементов?

4. Доказать, что (-у-) = 1, если р = 1 или 3 (mod 8); {—у) — —1, если р =. 5 или 7 (mod 8).

5. Найти (yjpf), используя закон квадратичной взаимности.

6. Найти гауссову сумму G — 5Z'l|(^)?J (где ? — корень q-й степени из 1 в поле Fpf , где р? = 1 (mod q)), если

а) 9 = 7, р = 29, / = !,? = 7;

б) д = 5, р = 19, / = 2, ? = 2 - 4г, где г — корень X2 + 1;

в) 9 = 7. P = 13, / = 2, ? = 4 + а, где а — корень .Y2 — 2.

7. Пусть m = а4 + 1, а 2. Найти такое натуральное х между 0 и т/2, что Xі = 2 (mod m). Воспользовавшись этим, найти \/2 в Fp в каждом из случаев: р = 17, 257, 65537 (простые числа Ферма); р = 41 = (З4 + 1)/2; р = 1297; р = 1201. (Указание: см. доказательство предложения П. 2. 4.)

8. Пусть р и q — простые числа, q = 1 (mod р). Пусть ? — примитивный корень р-й степени из 1 в Yq. В терминах ? найти формулу для квадратного корня из (=±)р в F,.

9. а) Пусть т = ар — 1, где р — нечетное простое число и a 2. Найти такое натуральное число г между 0 и т/2, что х2 = (-у)р (mod m). Использовать это

для нахождения у/ъ в F31, у/—7 в Fi 27, \/Тз в Fsi9l, \Jв Fio93-

б) Пусть q = 2P — 1 есть простое число Мерсенна. Найти выражение для такого наименьшего натурального числа 6, что 62 =. (-у-)р (mod q).

10. Вычислить символ Лежандра (|f§y): а) используя квадратичный закон взаимности только для символа Лежандра (т.е. разлагая на множители все появляющиеся числа), б) не разлагая на множители нечетные числа, т.е. используя квадратичный закон взаимности для символа Якоби.

11. Вычислить следующие символы Лежандра:

а) № б) (і?); в) (&); г) (&); д) (^^); е) (§§ff); ж) (ffffl).

12. а) Пусть р — нечетное простое. Доказать, что —3 является вычетом в Fp тогда и только тогда, когда р = 1 (mod 3).

б) Показать, что 3 является невычетом по модулю любого простого числа Мерсенна, большего 3.

13. Найти условие на последнюю десятичную цифру простого числа р, эквивалентное тому, что 5 — квадрат в Fp.

14. Доказать, что квадратичный вычет никогда не может быть образующим

bf;.

15. Пусть р — простое число Ферма.

а) Показать, что любой квадратичный невычет есть образующий в F*.

§ 2. КВАДРАТИЧНЫЕ ВЫЧЕТЫ И ЗАКОН ВЗАИМНОСТИ

59

б) Показать, что 5 — образующий в F*, если р ф 5.

в) Показать, что 7 — образующий в F*, если р ф 3.

16. Пусть р — простое число Мерсенна. Положим q = р2. Пусть г — корень Xі + 1 = 0, так что Fq = Fp(i).

а) Предположим, что целое число а2 + Ь2 — образующий элемент в F*. Показать, что тогда а + Ы — образующий для F*.

б) Показать, что как 4 + г, так и 3 + 2г являются образующими для F*l2.

17. Пусть р — нечетное простое число, а — целое число между 1 и р — 1. Оценить в терминах р число двоичных операций, требующихся для вычисления (~)'- а) ПРИ использовании квадратичного закона взаимности для символа Якоби и б) при использовании предложений II. 2. 2 и 1.3.6.

18. а) Пусть р — нечетное простое число, а, 6, с — целые числа и р I а. Доказать, что число решений і Є {0,1,2,. . .,у - 1} сравнения ах2 + Ьх + с = 0 (mod р) дается формулой 1 + (у), где D = Ь2 — iac есть дискриминант.

б) Сколько решений в Fg3 имеется для каждого из следующих уравнений: 1) X2 + 1 = 0; 2) X2 + X + 1 = 0; 3) X2 + 21Х -11 = 0; 4) X2 + X + 21 = 0; 5) X2 - AX - 13 = 0?

в) Сколько решений в F97 имеется для каждого из уравнений в части б)?

19. Пусть р — 2081 и п — наименьший положительный невычет по модулю р. Найти та и, используя описанный в § II.2 метод, вычислить квадратный корень из 302 по модулю р.
Предыдущая << 1 .. 24 25 26 27 28 29 < 30 > 31 32 33 34 35 36 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed