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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

83
α
α
μ
nn
qq
22
inflim)( =
−
,
где
lim inf
n
a
– наибольшее такое a , что неравенство
aa
n
<
выполняется
лишь конечное число раз, а
n
q
– знаменатель подходящих дробей для
α
.
6. Докажите, что для любого натурального
n
2
2
41111
242
4
nnn
n
nn
μμ
+−
⎛⎞
⎛⎞
+−
=+−=
⎜⎟
⎜⎟
⎜⎟
⎜⎟
+
⎝⎠
⎝⎠
,
2
2
4111
242
4
nnn n
n
nn
μμ
−+
⎛⎞
⎛⎞
+−
=+−=
⎜⎟
⎜⎟
⎜⎟
⎜⎟
+
⎝⎠
⎝⎠
.
7. Докажите, что для любого натурального числа
n минимальное на-
туральное число, представимое в виде
(
)
22
2nx n y−+
, где
y
x
,
– натуральные
числа, равно
n.
8. Пусть минимальное натуральное число, представимое в виде
22
Nx y− , где ,
x
y – натуральные числа, равно k. Докажите, что
)2/()( NkN =
−
μ
, а для любой дроби /pq, если /0Npq−>, то
(
)
NkqpN 2// >−
.
9. Докажите, что в условиях задания (8) для любых целого
Р и нату-
рального
Q
2
PQ Q
NN
μ
+
−
⎛⎞
≤
⎜⎟
⎝⎠
,
2
PQ kQ
NN
μ
−
−
⎛⎞
≤
⎜⎟
⎝⎠
,
2
PQ Q
NN
μ
+
+
⎛⎞
≤
⎜⎟
⎝⎠
,
2
PQ kQ
NN
μ
−
+
⎛⎞
≤
⎜⎟
⎝⎠
.
10. Решите уравнение Пелля
222
(( ) 2 ) 1xnm my
−=
.
11. Покажите, что решения уравнения Пелля (10) являются наимень-
шими возможными.
12. Докажите, что простое число вида
41k
+
представимо в виде сум-
мы двух квадратов натуральных чисел, причем единственным образом.
[Используйте результаты решения задания (10)].
23. Примитивные корни
23.1. Теорема. Предположим, что g является примитивным корнем
по
модулю n. Тогда:
а)
для некоторых целых чисел r и s, g
r
≡ g
s
(mod n) ⇔ r ≡ s (mod
φ
(n)),
б)
φ
(n), числа 1, g, g
2
, . . . , g
φ
(n)–1
– все являются различными по mod n.
Они, следовательно, являются числами, взаимно простыми с n.
23.2. Примеры
1. Ранее было найдено несколько решений конгруэнции а
р – 1
≡
≡ 1 (mod p
2
), где а было задано, а р представляло собой простое число. Если
задано
р и мы можем найти примитивный корень g mod p
2
(как мы увидим

Страницы