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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

49
3. Начиная с n
7
≡ n (mod 7), докажите, что n
13
≡ n (mod 7) для любо-
го n. Покажите аналогичным образом, что n
13
≡ n по модулю 5, 3 и 2. Дока-
жите, что для любого n (n
13
– n) делится на 2 · 3 · 5 · 7 · 13 = 2730.
4. Начиная с 2
16
≡ 1 (mod 17), докажите, что (2
10
)
6
≡ 1 (mod 17).
5. Пусть f(n) = n
6
+ 1091. Покажите, что если 3 не делит n, тогда 3 | f(n)
и, что, если 7 не делит n, тогда 7 | f(n). Докажите, что если n не кратно 42,
тогда f(n) есть составное число. Покажите также, что если n ≡ ± 2 (mod 5),
тогда 5 | f(n) делится на 5 (5 | f(n)), и докажите, что только единственно воз-
можными значениями n, для которых f(n) является простым – это те, кото-
рые имеют вид 210k или 210k ± 84. (Действительно, согласно [7], только
одно значение n меньшее 4000, а именно, 3906, даёт простое значение f(n).
Вы можете сократить несколько чисел с помощью хитрых приёмов, но ус-
тановить, что первое значение n = 210 · 19 – 84, делающее f
(n) простым,
достаточно сложно).
6. Пусть
4
1nr=+. Используйте малую теорему Ферма, чтобы пока-
зать, что n никогда не будет кратным 3, 5 или 7. [Например, число 5:
r
4
≡ 1 (mod 5) всякий раз, когда 5 не делит r. Так n ≡ 2 (mod 5), когда 5 не
делит r, и n ≡ 1 (mod 5), когда 5 | r ]. Можете ли Вы найти любой простой
делитель n? (Действительно, наименьшим простым числом, которое может
быть делителем, это 17. Только простые числа вида 4m + 1 могут быть де-
лителями n. Более точным ответом будет 8m
+ 1).
12.3. Упражнение: частные Ферма. Если р – простое число и р | a,
тогда, исходя из теоремы Ферма, (а
р-1
– 1)/р будет целым числом. Оно на-
зывается частное Ферма и обозначается как q
p
(a). Предлагаем проверить не-
сколько простых свойств.
1. Предположим, что p не делит a и p не делит b. Используйте
(a
p–1
– 1)(b
p–1
– 1) ≡ 0 (mod p
2
), чтобы показать, что
q
p
(ab) ≡ q
p
(a) + q
p
(b) (mod p).
2. Используйте биномиальную теорему, чтобы показать, что
q
p
(p – 1) ≡ 1 (mod p) и q
p
(p + 1) ≡ –1 (mod p).
12.4. Теорема.
Когда р – простое число, d ≥ 1 и d | (p – 1), то уравне-
ние x
d
≡ 1 (mod p) имеет точно d решением сравнения по (mod p).
12.5. Лемма. Пусть р будет простым числом и
f(x) = a
0
x
n
+ a
1
x
n-1
+ . . . + a
n
, где p не делит a
0
.
Тогда количество решений f(x) ≡ 0 (mod p), по крайней мере, равно n.
Заметим, что предположение относительно того, что р является про-
стым числом, необходимо. Например, х
2
+ х ≡ 0 (mod 6) имеет четыре реше-

Страницы