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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

11
– (140 – 50 · 2) = 50 · 3 – 140 = (330 – 140 · 2) 3 – 140 = 330 · 3 – – 140 · 7. Ко-
нечным результатом будет НОД = 10, выраженный в виде
as + bt, где реально
s = 3, а t = –7. Применяя этот метод к общему алгоритму, получим следующий
результат.
3.8. Теорема.
Пусть (a, b) = h. Тогда существуют целые числа s и t,
такие, что as + bt = h.
3.9. Вывод. (a, b) = 1, если и только если существуют целые числа s и
t, такие, что as + bt = 1.
3.10. Упражнения
1. Подтвердите результат, что если a | bc и (a, b) = 1, тогда a | c, запи-
сывая
as + bt = 1 и умножая на с.
2. Предположим, что (
a, b) = 1 и с | (a + b). Покажите, что (c, a) =
= (
c, b) = 1.
3. Пусть
a = bq + r, 0 ≤ r < b, как в основном шаге алгоритма Евклида.
Проверьте, что для
n > 1 и а > 0, n
a
– 1 = (n
b
– 1)(n
b(q–1)+r
+ n
b(q-2)+r
+ . . .
+
n
b+r
+ n
r
) + n
r
– 1.
Представьте это как
A = BQ + R. Почему 0 ≤ R < B ? Докажите, что
шаги алгоритма Евклида для (
А, В) = (n
a
– 1)(n
b
– 1) точно следуют алгорит-
му Евклида для (
a, b) c заменой каждого r
i
на n
ri
– 1. Докажите, в частности,
что (
n
a
– 1, n
b
– 1) = n
(a, b)
– 1.
4. Разделите (
a
n
– b
n
)/(a – b) = a
n
+ a
n-1
b + a
n –2
b
2
+ . . . + b
n
на a – b и
выведите, что
1
,(,)
nn
n
ab
ab abnb
ab
−
⎛⎞
−
−=−
⎜⎟
−
⎝⎠
.
Более трудная задача: используйте этот результат, чтобы показать,
что тот же самый НОД равняется (
a – b, n(a, b)
n–1
). Одной возможностью
является показать, что
nb
n–1
в вышеприведенном уравнении может быть за-
менено на
na
k
b
n–k
для k = 1,2, …, n. Тогда представим h = (a, b), sa + tb = h и
покажем, что каждый общий делитель
a – b и nb
n–1
также делит nh
n–1
.
5. Пусть
s
0
> a > 0 будут целыми числами, (s
0
, a) = 1 и определим s
n
для
n = 1, 2, 3, . . . как s
n
= a + s
n–1
(s
n-1
– a). Покажите, что s
n
– a = s
0
s
1
s
2
. . . s
n–1
(s
0
– a) для n ≥ 1.
Далее покажите, что если
n > m ≥ 0, тогда s
n
и s
m
будут взаимно про-
стыми числами. Как особый случай, возьмите
s
0
= 3, a = 2. Покажите ин-
дукцией, что
2
21
n
n
s =+
. (Это является n-м числом Ферма, о котором было
упомянуто выше).
6. Рассмотрим первый шаг алгоритма Евклида в виде
a = bq + r, где
мы примем, что
a > b > 0, что означает q ≥ 1. Если b ≤ a/2, тогда, конечно,

Страницы