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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

90
степень р – делителя n, где k ≥ 2. Используйте φ(p
k
) |
λ
(n), чтобы показать, что
p | (n – 1). Это противоречие показывает, что n является произведением различ-
ных нечётных простых чисел. Наконец, используйте
φ(p) = (р – 1) |
λ
(n), чтобы
показать, что для каждого простого числа
p | n у нас будет (p – 1) | (n – 1).
Это доказывает, что
n является числом Кармайкла, если и только если
n = q
1
q
2
. . . q
k
, k ≥ 2, где q
i
являются различными нечётными простыми
числами и для каждого
i (q
i
– 1) | (n – 1).
23.18. Упражнения
1. Найдите наименьший квадратичный невычет по mod p для простых
чисел 17, 19, 997, 1 000 333, 10 000 993, используя написанную Вами про-
грамму расчета. Далее решите сравнения:
х
2
≡ 15 (mod 17), х
2
≡ 11 (mod 19), х
2
≡ 589 (mod 997),
х
2
≡ 3 (mod 1000333), х
2
≡ 2 (mod 10000993).
2. Испытайте правило Шэнкса относительно того, что в среднем в
двух третях случаев не требуется совсем повторения:
х
0
является решением.
3. Почему максимум возможного числа шагов алгоритма Шэнкса ра-
вен
s
0
? Здесь приведено несколько примеров, где (достаточно просто!)
сравнение требует максимального числа итераций; конечно, Вы можете
найти больше. В каждом случае найденный невычет равен 3, а сравнением
будет
х
2
≡ 9.
по mod 17:
s
0
= 4; по mod 257: s
0
= 8;
по mod 65537:
s
0
= 16; по mod 167 772 161: s
0
= 25.
4. Предположим, что р является нечётным простым числом, k ≥ 2, p не
делит
a и х
1
является решением
х
2
≡ а (mod p
k
), 0< х < p
k
. (1)
5. Покажите, что
х
1
может быть представлено единственным образом
как
х
1
= х
2
+ sp
k–1
, где 0 ≤ s < p, a x
2
является решением сравнения
х
2
≡ а (mod p
k–1
), 0 < х < p
k-1
. (2)
6. Предположим, что
x
2
удовлетворяет (2). Покажите, что х
1
= х
2
+ sp
k–1
удовлетворяет (1), если и только если
()
p
p
ax
sx
k
mod2
1
2
2
2
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
−≡
−
.
Здесь правая часть (
не является символом Якоби!) будет целым чис-
лом, так как
х
2
удовлетворяет (2). Докажите, что х
1
единственным образом
определяется
х
2
.

Страницы