Элементы теории чисел и криптозащита. Воронков Б.Н - 91 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

91
7. Докажите, что сравнение (1) имеет то же число решений, что и
х
2
≡ а (mod p), а именно, два, если
a
p
⎛⎞
⎜⎟
⎝⎠
= 1, и не имеет решений
в противоположном случае.
8. Что будет, если
p | a?
9. Решите сравнения, где
р замените на р
2
в вышеприведённом п. 6
этого упражнения. Последнее из них,
х
2
≡ 2 (mod 10 000 993
2
= 100 019 860 986 049)
выполнимо, если воспользоваться расширенной точностью (extended), но
Вам будет необходим алгоритм Хэда для проверки точности ответа! Отве-
том будет
x = 33 406 487 105 406 (и s = 3 340 317).
10.
Найти решение сравнения х
2
≡ а (mod 2
k
). Метод, данный в п. 7 не
будет здесь работать, но некоторые изменения получаются за счёт хитрых
приемов. Случаи
k = 1 или 2, мы оставим решать Вам! Также необходимо
рассмотреть случай, когда
а – нечётное число (в противном случае k может
быть сокращено), что означает, что все решения являются также нечётны-
ми.
Отсюда и далее мы условимся, что а является нечётным, и k ≥ 3.
11. Предположим, что
х
2
≡ а (mod 2
k
). (3)
Используя тот факт, что любой квадрат сравним с 1 (mod 8), покажи-
те, что
х
2
≡ 1 (mod 8). Отсюда и далее мы примем, что это выполняется.
12. Покажите, что если
х и у оба являются решениями сравнения (3),
тогда
22
x
yx y−+
⋅
≡ 0 (mod 2
k–2
). Докажите, что 2
k–2
является делителем одно-
го из сомножителей и, отсюда, что
х ≡ ±у (mod 2
k-1
). Докажите, что если
существует одно решение
х уравнения (3), тогда существуют ровно четыре
решения по (mod 2
k
), а именно, ± х и ±х + 2
k–1
.
13. Начав с решения
х = 1 сравнения (3), когда k = 3 (вспомните, что
а ≡ 1 (mod 8)), сконструируйте решение (3) для любого k. [Подсказка.
Пусть
х
2
удовлетворяет х
2
≡ а (mod p
k–1
). Вместо написанного в п. 7 х
1
= х
2
+
+
s ⋅ 2
k–1
запишите х
1
= х
2
+ s ⋅ 2
k–2
(почему это является улучшением?). По-
кажите, что для того, чтобы
х
1
удовлетворял уравнению (3), нам необходи-
мо, чтобы
s
= (
2
2
х – a)/2
k–1
(mod 2)].
Докажите, что уравнение (3) имеет точно четыре решения для любого
k ≥3.

Страницы