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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

15
3.15*. Упражнение. Оно основывается на результат (но не програм-
му) п. 3.14, так что примем, что имеются
a и b (>0) при (a, b) = 1, тогда все
числа
m > ab – a – b могут быть представлены в виде ax + by для x ≥ 0 и
y ≥ 0. Представьте, что у Вас имеется большое количество прямоугольных
плиток размером
a × b, где a и b – различные простые числа (следовательно,
взаимно простые), и дан прямоугольник m
× n, где m и n – оба > ab – a – b.
Идея заключается в том, чтобы покрыть всю площадь прямоугольника
m
× n плитками a × b. Конечно, это потребует ab | mn. Задача выполнима,
если
ab | mn, тогда покрытие плитками возможно. Заметим, что, так как a и
b – простые числа, условие ab | mn даёт исключительно две возможности:
a | m и b | n, или a и b оба делят m. Покажите, что в первом случае покрытие
плитками возможно (это просто)! Теперь обратимся ко второму случаю, на-
чиная с выбора
w, x, y, z (все ≥ 0), таких, что aw + bx = m и ay + bz = n. Ко-
нечно, Вам, может быть, больше по душе подумать о более малых значени-
ях
m и n: возможно ли покрытие плитками, если ab | mn? Что будет, если a и
b не будут простыми числами?
3.16. Проект: число шагов в алгоритме Евклида
Существует теорема: для «большинства» пар a, b использование
алгоритмa Евклида потребует около (12 ln 2/
π
2
)ln b шагов. Проверьте это,
задавая произвольные значения чисел
a и b.
3.17. Минимальные представления и алгоритм Евклида
(Это доказательство дано Дж. У. Брюсом). Предположим, что a и b
являются положительными и взаимно простыми числами, и воспользуемся
алгоритмом Евклида для нахождения
s и t таких, что as + bt = 1. Конечно,
можно и другими способами выбрать
s и t; действительно, общим решением
будет
a(s + rb) + b( t – ra) = 1 для некоторого r. Определим «размер» этой
выборки как
f (r) = (s + rb)
2
+ ( t – ra)
2
. Следуя далее нашей интуиции, мы
можем показать, что
минимальное значение всегда достигается для r = 0:
алгоритм Евклида минимизирует «размер» коэффициентов. В данном слу-
чае
f (r) = r
2
(a
2
+ b
2
) + r(2 sb – 2ta) + ( s
2
+ t
2
) становится квадратичным по r.
Таким образом, минимумом, достижимым для
r, будет единственное значе-
ние
r.
1. Показать, что минимальное значение
f (r) достигается при r = 0,
почему для этого достаточно доказать, что
f(1) ≥ f(0) и f(–1) ≥ f(0)?
2. Покажите, что условия п. 1 выполняются, если и только если |2
sb –
– 2
ta| ≤ a
2
+ b
2
. Для этого достаточно показать, что когда используется алго-
ритм Евклида для нахождения
s и t, a ≥ |2t | и b ≥ |2s |. Это достигается по
индукции на определённом шаге алгоритма Евклида.
3. На первом шаге выберем (
b > 1), a = bq + 1, так что s = 1, а t = – q.
Проверьте результат в этом случае.

Страницы