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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

86
4. Пусть n = 4 h, где h > 1. Покажите, что а = 2 h + 1 приводит
к
а
2
≡ 1 (mod 4h). Покажите также, что а не сравнимо с 1 (mod 4h), и дока-
жите, что не существуют примитивные корни по mod
n для вышеприведён-
ного п. 22,3 (4).
5. Пусть
g будет примитивным корнем по mod p для простого числа р,
так что по (mod
p)
1,
g, g
2
, . . . , g
p–1
(1)
являются числами 1, 2, . . . ,
р – 1 в некотором порядке. Покажите, что раз-
ностии
g – 1, g
2
– g, . . . , g
p–2
– g
p–3
, 1 – g
p–2
являются по (mod p) цикличе-
скими перестановками (1).
6. Пусть
р = 4n + 3 будет простым числом и примем, что а
(р–1)/2
≡
≡ 1(mod р). Покажите, что х = ±a
n+1
удовлетворяет х
2
≡ а (mod p). Так как
это
а конгруэнтно квадрату по (mod p), мы назовём а квадратичным выче-
том
по mod p.
7. Пусть
p = 8n + 5 будет простым числом и примем а
(р–1)/4
≡ 1(mod р).
Проверьте, что
х = ±a
n+1
удовлетворяет х
2
≡ а (mod p). Это а также является
квадратичным вычетом по mod
p.
8. Пусть
р будет нечётным простым числом и предположим, что суще-
ствует
m, такое, что для всех а, для которых p не делит a, получим а
m
≡
≡ 1(mod р). Заметим, что выбор а = – 1 показывает, что m является чётным.
Предположим, что для некоторого
а с p | a у нас будет а
m/2
≡ 1(mod р). Выби-
рая
g примитивным корнем по mod p, покажите, что g
т/4
≡ – 1(mod р), и что
точно половина р – 1 чисел а = 1, 2, . . . , р – 1 удовлетворяет сравнению
а
m/2
≡ 1(mod р), а другая половина удовлетворяет а
m/2
≡ –1(mod р).
Два вышеприведённых упражнения (7) и (8) близко связаны со сле-
дующим результатом, который даёт широкие возможности для его исполь-
зования в последующем. Пусть
р будет нечётным простым числом и пусть g
будет примитивным корнем по mod
p. Пусть p не делит a, так что
а ≡ g
k
(mod р) для некоторого k, который единственным образом определён
по mod (
p – 1). Так как р – 1 является чётным числом, то можно смело ска-
зать, что
k будет чётным или нечётным. Также а
р–1
≡ 1(mod р), исходя из
теоремы Ферма, так что р, будучи простым (и нечётным!), удовлетворяет
сравнению
а
(р–1)/2
≡ ±1(mod р). Тогда мы получим следующее:
23.8. Теорема
. Для принятой системы обозначений
а)
k является чётным ⇔ а
(р–1)/2
≡ 1(mod р) ⇔ а ≡ х
2
(mod р) для некото-
рого
х;
б)
k является нечётным ⇔ а
(р–1)/2
≡ – 1(mod р) ⇔ а не сравнимо
с
х
2
(mod р) для всех х.
Следовательно, мы имеем следующий результат, в котором не упоми-
нается примитивный корень
g:

Страницы