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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

12
r < a/2. Принимая b > a/2, покажите, что r остается меньше a/2. Почему этот
аргумент означает, что если для некоторого
i ≥ 0 r
i+2
< r
i
/2, то r
i
> 0? (Здесь
r
0
= a, r
1
= b). Таким образом, если остатки остаются ненулевыми, мы имеем
r
3
< r
1
/2, r
5
< r
3
/2, . . . Докажите, что r
2n+1
= 0, если n достаточно большое для
обеспечения условия 2
n
≥ b. Приведите несколько примеров для оценки
влияния этой верхней границы на длину алгоритма по сравнению с дейст-
вительной длиной.
7. Пусть
a и b целые числа, оба не равные нулю. Рассмотрите ряд чисел
S = {ax + by: x и y – целые числа}. Пусть h будет наименьшим элементом S,
который больше нуля. Записав
a = qh + r, 0 ≤ r < h, покажите, что r ∈ S и до-
кажите, что
h|b. Покажите также, что любое общее кратное a и b является
кратным
h и покажите, что h = (a, b). Заметим, что это доказывает снова тео-
рему 3.8, но он не является достаточно полезным путем для действительного
нахождения целых чисел
s и t при as + bt = (a, b).
8. Используйте результат задания 3 упражнения 3.10, чтобы показать,
что, если (
a, b) = 1, то (R
a
, R
b
) = 1, где R
a
является десятичным числом (10
а
–
– 1)/9, содержащим
a разрядов. Для общего случая покажите, что
(
R
a
, R
b
) = R
(a, b)
.
9. Пусть
m и n будут взаимно простыми числами и пусть u, v будут
натуральными числами и
nv – mu = 1. Проверьте, что x = a(a
m
+ b
m
)
u
, y =
= b
(a
m
+ b
m
)
u
, z = (a
m
+ b
m
)
v
являются решением уравнения x
m
+ y
m
= z
n
. [От-
сутствие решений при
m = n ≥ 3 является знаменитой догадкой, обычно на-
зываемой последней теоремой Ферма].
10. Пусть
p и q различные простые числа и пусть n > 1. Почему долж-
ны
n
p
– 1 и n
q
– 1 оба делить n
pq
– 1? Используйте результат задания 3 уп-
ражнения 3.1 и решение задания 6 упражнения 2.2, чтобы показать,
что
(1)(1)
(1)(1)
pq
pq
nn
N
nn
−−
=
−−
является целым числом.
3.11. Упражнение: линейные диофантовы уравнения
Рассмотрим уравнение
ax + by = d, (1)
где
a, b, x и y являются целыми числами, причем, a, b не равны нулю. Оты-
щем полный ряд
x, y решений уравнения (1). Пусть (a, b) = h, a = a
1
h, b =
=
b
1
h, так что (a
1
, b
1
) = 1.
1. Покажите, что если
h не делит d, тогда выражение (1) не имеет ре-
шений вида [
h | левая часть уравнения (1)].
2. Предположим теперь, что
h | d, d = d
1
h; тогда предположим, что
справедливо уравнение
a
1
x + b
1
y = d
1
. (2)
Выберем
s, t такими, чтобы a
1
s + b
1
t = 1, а x = sd
1
, y = td
1
являлось од-
ним решением. Покажите, что если
X, Y будет другим решением, тогда

Страницы