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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

88
Таким образом, начиная, скажем, с а = 2, вычислим а, а
2
, а
3
, . . . , по
(mod
p), пока первое число, конгруэнтное 1 будет а
r
, так что r = ord
p
a. Если
r = p – 1, то стоп! Другим способом принимают b первым числом, для кото-
рого 2 <
b < p – 1, и b не конгруэнтно ни одной степени а. Пусть s будет по-
рядком
b(mod p). Если s = p – 1, тогда Вам необходимо взглянуть дальше! В
одном случае выполняется, что
s | r. [Доказательство: если s | r, тогда
b
r
≡ 1 (mod p). Но 1, а, . . . , а
r–1
являются спаренными конгруэнтными реше-
ниями сравнения (
x r) ≡ 1(mod p), а эта конгруэнция имеет точно r решений,
так что
b должно иметь степенью а]. Таким образом, НОК(r, s) > r. Тогда
получим
r = ux, s = vy при (u, v) = 1 и uv = НОК(r, s), и рассмотрим
c ≡ a
x
b
y
(mod p). Это с должно иметь порядок uv = НОК (r, s) > r. Если
uv = p – 1, тогда процедура заканчивается, а с является примитивным кор-
нем, в противоположном случае начинаем, но с числа
с, вместо а.
23.14. Проект: конструкция примитивного корня по mod p. Напи-
шите программу, иллюстрирующую вышеприведённый метод. Для сле-
дующих простых чисел Вы должны получить представленные примитивные
корни:
р 7 41 73 191 311 479
корень 3 7 5 189 309 477
Обратите внимание, что в последних трёх случаях – 2 является при-
митивным корнем.
Заметьте, что вышеизложенный метод непрактичен для больших про-
стых чисел только из-за проблемы хранения; программа должна записывать
степени
а до того, как вычет 1 будет достигнут, а для этого необходимы, ни
много, ни мало,
р – 1 из них.
Когда у
n есть примитивный корень, скажем, g, тогда порядок g будет
φ
(n), и, используя теорему Эйлера для некоторого а, для которого (a, n) = 1,
мы получим ord
n
a |
φ
(n). Естественно спросить, какой соответствующий ре-
зультат будет, когда (если случайно произойдёт)
n не имеет примитивного
корня. Заменит ли минимальный универсальный показатель
λ
(n) функцию
Эйлера
φ
(n) в этом случае? Таким образом, нам бы хотелось, чтобы
ord
n
a |
λ
(n) для всех а, взаимно простых с n, и чтобы существовал некото-
рый
а, для которого ord
n
a =
λ
(n).
Рассмотрим, например,
n = 800 = 2
5
5
2
, для которого
φ
(n) = 320. Ис-
пользуя ранее рассмотренный п. 22.12 (1),
а
8
≡ 1 (mod 2
5
) для некоторого
нечётного
а. Согласно теореме Эйлера, а
20
≡ 1 (mod 5
2
) для некоторого а,
удовлетворяющего условию 5 не делит
a. Таким образом, для некоторого а,
(
а, n) = 1, мы получим а
40
≡ 1 (mod 2
5
5
2
), а 40 является НОК 8 и 20. Сущест-
вует ли значительно меньшая степень
а, которая тоже сравнима с 1 (mod n).

Страницы