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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

87
в) критерий Эйлера для квадратичных вычетов:
х
2
≡ а (mod р) имеет решение для х ⇔ а
(р-1)/2
≡ 1(mod р).
23.9. Теорема. Пусть р будет простым числом. Тогда
а) е
сли g является примитивным корнем по mod p, то либо g, либо
g + p является
примитивным корнем по mod p
2
;
б) е
сли g является примитивным корнем по mod p
2
, то g будет при-
митивным
корнем по mod p
k
для k ≥ 1;
в) е
сли g является нечётным (соответственно, чётным) примитив-
ным корнем
по mod p
k
, то g (соответственно, g + p
k
) будет примитивным
корнем
по mod 2p
k
.
23.10. Теорема. Число n обладает примитивным корнем, если и
только если
n = 1, 2, 4, p
k
или 2p
k
для нечётного простого числа р и k ≥ 1.
23.11. Компьютерное упражнение. Найдите наименьшее число g,
для которого
g является примитивным корнем по mod 29, но не по mod 29
2
.
Покажите, что наименьшее простое число
р, для которого 10 является при-
митивным корнем по mod
p
2
, есть р = 487.
23.12. Упражнения
1. Покажите с помощью простой индукции по k, что для а нечётного и
k ≥ 3, a↑2
k–2
≡ 1 (mod 2р
k
). (Напишите а↑2
k–2
= 1 + r2
k
и квадрат).
2. Покажите с помощью индукции по
k, что для k ≥ 3, 3↑2
k–2
≡ 1 (mod 2
k
).
(Действительно, это справедливо также для
k = 2, но Ваш первый шаг, вероят-
но, будет 3
↑2
k–2
≡ 1 (mod 2
k
), исходя из пункта (1), а это требует k ≥ 3).
3. Покажите с помощью индукции по
k , что для k ≥ 3 порядок
3 mod 2
k
равняется 2
k–2
.
23.13. Проект. Напишите программу для определения наименьшего
примитивного корня по mod
p для любого p < 200. (Большинство таких
наименьших примитивных корней являются совсем маленькими числами;
единственное исключение
р = 191, для которого Вы найдёте 19 – наимень-
ший примитивный корень.
Полезно рассмотреть один метод, помимо чисто силового, с помощью
которого можно, в принципе, найти примитивный корень
g для некоторого
нечётного простого числа
р. Идея заключается в том, чтобы начать с неко-
торого предполагаемого
а, такого, как а = 2, и, если это не примитив, полу-
чить следующие числа с последовательно увеличивающимся порядком по
mod
p. В конце концов (а обычно, достаточно быстро) получим примитив-
ный корень, хотя, не обязательно, наименьший.

Страницы