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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

71
сos(
α
), сos(2
α
), сos(2
2
α
), сos(2
3
α
), . . .
имеет только ограниченное число различных членов.
Полученный выше результат п. 18.3 (1) показывает, что мы часто
имеем меньшую степень а, чем степень
φ
(n), которая сравнима с 1 (mod n).
Действительно, показано, что если n делится на два различных нечётных
простых числа, то так всегда происходит для любого числа а, взаимно про-
стого с n. Мы получили достаточное количество информации, чтобы разо-
брать следующее понятие.
19.4. Определение. Пусть (a, n) = 1. Наименьшее число k > 0, такое
что a
k
≡ 1 (mod n), называется порядком a по mod n. Это записывается как
k = ord
n
a, и мы также скажем, что а имеет порядок k по mod n. Конечно,
ord
n
a ≤
φ
(n). Заметим, что если (a, n) > 1 и k > 0, то невозможно для a
k
быть
сравнимым с 1 по mod n. Если а имеет порядок k по (mod n), тогда
в некоторых книгах используют выражение «а принадлежит показателю
k (mod n)».
19.5. Теорема. Предположим (a, n) = 1. Тогда a
k
≡ 1 (mod n), если и
только если ord
n
a | k. Отсюда степень а, которая сравнима с 1, не только
≥ ord
n
a, но точно кратна этому порядку. В особенности, ord
n
a |
φ
(n) и, ес-
ли р – простое число, то ord
p
a | (p – 1).
19.6. Упражнения
1. Пусть n = 12, так что
φ
(n) = 4. В соответствии с п. 19.5, порядок по
mod 12 некоторого числа а, для которого (а, 12) = 1, должен быть 1, 2 или 4.
Найдите все возможные порядки. Равны ли они 4? (Обратитесь к п. 19.3 (4)).
2. Покажите, что порядком 2 mod 11 будет
φ
(11) = 10. Чтобы доказать
это, будет достаточно показать, что
2
k
не сравнимо с 1 (mod 11) для k = 2 и
5, которые являются собственными делителями 10. Что будет порядком
2 mod 22? Покажите, что 7 и 13 оба имеют порядок
φ
(22) = 10, mod 22.
3. Покажите, что не существует числа
а, для которого ord
4
a =
φ
(8) = 4.
Предсказано ли это в п. 19.3 (4)? Существует ли
а с ord
4
a =
φ
(4) = 2? Найди-
те все числа
а с ord
7
a =
φ
(7) = 6 и все числа b c ord
14
b =
φ
(14) = 6.
4. Пусть
р будет простым числом, и предположим, что а имеет поря-
док 3 mod
p. (Заметим, что это означает, что 3 | (p – 1), и, так как р должно
быть нечётным, из этого следует, что 6 | (
p – 1)). Покажите, что
а
2
+ а + 1 ≡ 0 (mod p) и докажите, что (а + 1)
6
≡ 1 (mod p). Покажите, что,
в действительности,
а + 1 имеет порядок точно 6 mod p.
5. Пусть
р будет простым числом и предположим, что a имеет поря-
док
n mod p
k
и порядок m mod p
k –1
, где k ≥ 2. Покажите, что n = m или
n = mр. [Сначала покажите, что а
n
≡ 1 (mod p
k–1
) и докажите, что m | n. Тогда
используйте, что
а
m
= 1 +
λ
p
k–1
для некоторого целого
λ
, и биномиальную

Страницы