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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

72
теорему, чтобы показать, что а
mp
≡ 1 (mod p
k
). Выведите из этого, что n | mp.
Результат следует из
m | n и n | mp].
6. Пусть
р будет простым числом и предположим, что а имеет порядок n
mod
p
2
и m mod p. Покажите, что m = n, если и только если а
р–1
≡ 1 (mod p
2
).
[Дело здесь в том, что, если
а
р–1
≡ 1 (mod p
2
), тогда n | (p – 1); теперь исполь-
зуйте результат пункта (5) при
k = 2]. Позднее, мы покажем, как, в принципе,
мы можем найти те значения, которые удовлетворяют сравнению для задан-
ного значения
р. Задавая конкретное а, например, а = 2, достаточно редкий
случай для простого числа
р удовлетворять сравнению (см. ниже, п. 19.8).
7. Предположим, что
р – простое число и а
р-1
≡ 1 (mod p
2
), а
а
т
≡ 1(mod p). Покажите, что а
т
≡ 1 (mod p
2
). [Пусть r = ord
p
a; возьмите р –
– 1 =
rk и m = rh, a
r
= 1 + cp. Используйте первую гипотезу, чтобы показать,
что
p | c, затем возьмите a
m
= (1 + cp)
h
и используйте биномиальную теорему].
8. Предположим, что
р – простое число, и р | F
k
, где F
k
=
2
21
k
+ является
k-м числом Ферма. Покажите, что ord
p
2 = 2
k + 1
, и докажите, что 2
k + 1
| (p – 1).
9. Пусть (
m, n) = (x, m) = (x, n) = 1 и пусть a = ord
m
x, b = ord
n
x. Пока-
жите, что
х
k
≡ 1 (mod mn), если и только если a | k и b | k. Докажите, что
ord
mn
x = HOK (a, b).
10. Пусть
a = ord
m
x и пусть s ≥ 1. Покажите, что ord
n
(x
s
) =
a
as(,)
. [Это
равносильно доказательству, что
),( sa
a
| t ⇔ (x
s
)
t
= 1].
19.7. Определение. Число а, для которого (a, n) = 1 и ord
h
a =
φ
(n) на-
зывается
примитивным корнем по mod n. Таким образом, в соответствии с
п. 19.3 (4), если
n делится на два различных простых нечётных числа, то оно
не имеет примитивного корня. Исходя из изложенного в п. 19.6 (3), число 8
не имеет примитивного корня. Для простого числа
р условие для а быть
примитивным корнем по mod
p должно быть ord
h
a = р – 1. Более подробно
примитивные корни разберём позже.
19.8. Проект. Проверьте, что а
р–1
≡ 1 (mod p
2
), когда а = 5, а р будет
одним из простых чисел 20 771, 40 487, 53 471 161. Найдите наименьшее
простое число
р, для которого это произойдёт, а) когда а = 3, б) когда а = 2
и в) когда
а = 11. Найдите другие решения для а < 50. [Существует экстра-
ординарная связь с «последней теоремой Ферма», описанная А. Виферихом
в 1909 г. Если
x
p
+ y
p
= z
p
, где р будет нечётным простым числом, которое
не является делителем положительных целых чисел
x, y, z, тогда 2
p–1
≡
≡ 1 (mod p
2
). Конечно, «последняя теорема Ферма» состоит в том, что не
существует решений для
р > 2].

Страницы