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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

85
23.3. Упражнения
1. Убедитесь, что 2 является примитивным корнем по mod 11
2
и по
mod 13
2
. (Возможно, ценно использовать короткие программы для вычис-
ления порядка, просто умножая 2 на себя и сокращая по mod
p
2
каждый раз,
пока не достигнут результат). Как и в вышеприведённом п. 22.2 (а), убеди-
тесь, что решениями для
а
р-1
≡ 1 (mod p
2
) будут р = 11, для а ≡ 1, 3, 9, 27,
40, 81, 94, 112, 118, 120 (mod 121). Используйте соответствующую про-
грамму, чтобы вычислить степени 2. Найдите решения для р = 13.
2. Убедитесь, что 7 является примитивным корнем по mod 22. Отсюда
найдите все решения
х для 19
х
≡ 17 (mod 22).
3. Проверьте, что 3 является примитивным корнем по mod 17, отсюда,
покажите, что 7
х
≡ 6 (mod 17) ⇔ х ≡ 13 (mod 16).
4. Убедитесь, что 5 является примитивным корнем по mod 18, отсюда,
покажите, что 13
х
≡ 7 (mod 18) ⇔ х ≡ 2 (mod 3).
5. Предположим, что
g является примитивным корнем по mod n, где
n > 2. Покажите, что х
2
≡ 1 (mod n) имеет точно два решения (напишите х ≡
≡ g
k
), и докажите, что х
2
≡ 1 (mod n) ⇔ х ≡ ± 1 (mod n).
23.4. Лемма. Единственно возможными числами n, которые могут
обладать примитивнвными
корнями, являются те, которые имеют вид:
n = 2
k
или р
т
, или 2 р
т
, где k ≥ 0, m > 0 и р – нечётное простое число.
23.5. Теорема. Предположим, что а является примитивным корнем
по mod 2
k
для некоторого k ≥ 3. Тогда а также и примитивный корень по
mod 2
k – 1
. Отсюда, не существуют примитивные корни по mod 2
k
для k ≥ 3.
23.6. Теорема. Пусть р будет нечётным простым числом, и d | (p – 1).
Пусть
ψ
(d) = #{x: 1 ≤ x ≤ p и ord
p
x = d}. Тогда
ψ
(d) =
φ
(d). В особенности,
ψ
(р – 1) =
φ
(р – 1): число примитивных корней по mod p точно равно
φ
(р – 1).
(
Заметим, что это справедливо и для р = 2).
23.7. Упражнения
1. Сколько примитивных корней существует по mod 11 ? Найдите все.
Выполняется ли это для mod 13. Для
р = 13 проверьте результат п. 22.3 для
всех делителей
d чисел р – 1.
2. Пусть
р будет простым числом, сравнимым с 1 (mod 4). Используя
п. 22.1, объясните, почему должен существовать элемент
х порядка
4 (mod
p)? Докажите, что х
2
≡ –1 (mod p). Почему такое не может существо-
вать для
х, когда р ≡ 3 (mod 4) ?
3. Пусть
g будет примитивным корнем по mod p для простого числа р
вида 8
n + 1. Почему g
2n
≡ 1 и g
4n
≡ –1 (mod p) ? Пусть х = g
n
± g
7n
. Покажите,
что
х
2
≡ ±2 (mod p), где знаки + и – являются аналогичными.

Страницы