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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

84
ниже, частично это всегда выполняется), тогда относительно просто найти
все значения, которые удовлетворяют конгруэнции. Так как (
а, р
2
) должно
быть 1 для конгруэнции, имеющей некоторые решения, мы уверены, что
а ≡
≡ g
x
(mod p
2
) для некоторых значений х, исходя из теоремы 22.1 (б).
Действительно
а
р – 1
≡ g
(p – 1)x
(mod p
2
), которое будет ≡ 1 (mod p
2
), ес-
ли и только если (
р – 1)х ≡ 0 (mod
φ
(p
2
) = p(p – 1)). Это выполняется, если и
только если х
≡ 0 (mod p), так что решениями будут а ≡ g
x
(mod p
2
), где
х = 0, р, 2р, . . . , (р – 2)р. Например, для
р = 7 просто проверить, что 3 явля-
ется примитивным корнем (по mod 49, а также, фактически, по mod 7), и эти
решения дают
а = 1, 18, 19, 30, 31, 48 (mod 49). Конечно, для чётного р – 1,
если
а является решением, тогда им будет (–а).
Заметим, что всегда имеется точно (
р – 1) различных решений
по (mod
p
2
). Действительно справедливо, что а
р-1
≡ 1 (mod p
k
) имеет точно р –
– 1 различных решений по (mod
p
k
) для k ≥ 1. Это может быть сравнимо по
сложности с нахождением
р для сравнения а
р-1
≡ 1 (mod p
2
) при заданном а.
2. Решите уравнения 12
х
≡ 17 (mod 25) и у
9
≡ 17 (mod 25). Действитель-
но, 2 является примитивным корнем по mod 25, как видно из следующей
таблицы, показывающей степени 2 по mod 25. Вспомните, что
φ
(25) = 20.
0 1 2 3 4 5 6 7 8 9
k
6 4 2 4 3 1 7 8 1 2 9 3
Представленные результаты не только показывают, что 2 является
примитивным корнем, так как 2
k
не сравнимо с 1 (mod 25) для 0 < k < 20, но
они представляют решение сравнения 2
k
≡ b для каждого b, взаимно просто-
го с 25. (В такой ситуации иногда говорят, что
b имеет индекс k по моду-
лю 25). Индексы имеют тесную связь логарифмами, так как для перемно-
жаемых чисел складываются их индексы.
Возвратимся к сравнению 12
х
≡ 17 (mod 25). Так как по mod 25, 12 ≡
≡ 2
9
и 17 ≡ 2
13
, как видно из таблицы, мы можем переписать это, как 2
9х
≡
≡ 2
13
(mod 25), и, как следует из п. 22.1 (а), это эквивалентно 9х ≡
≡ 13 (mod 20). Решая это обычным способом (т. е., 9 × 9 ≡ 1 (mod 20)), полу-
чим
х ≡ 17 (mod 20).
Так как
у
9
≡ 17 (mod 25), мы заметим, что это означает (у, 25) = 1, так
что можно написать
у ≡ 2
х
(mod 25), и уравнение читается как
2
9х
≡ 2
13
(mod 25), которое, как ранее, даёт х ≡ 17 (mod 20). Таким образом,
используя таблицу, получим
у ≡ 22(mod 25).

Страницы