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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

14
Определим r
0
= a, r
1
= b. Тогда r
i
= as
i
+ bt
i
для i ≥ 0, и в особенности,
(
a, b) = as
n
+ bt
n
. (Вспомните, что в алгоритме Евклида r
n
является послед-
ним ненулевым остатком и есть НОД
a и b).
3.13. Компьютерные упражнения
1. В случае, когда (a, b) = 1, пусть программа обеспечивает получение
чисел
s, t, таких, что as + bt = 1, т. е., as – 1 является кратным b. Такое s на-
зывается числом,
обратным (инверсией) по модулю b. Примем b > 0. Иногда
удобно добавить сомножитель
b к s: a(s + mb) + b( t – am) = 1, таким обра-
зом, что 0
≤ s
′
= s + mb < b. Другой путь написания этого s′ есть s – b[s/b].
Напишите программу для получения «наименьшей положительной инвер-
сии»
s′. Опасайтесь того, что конечное значение s2 может быть отрицатель-
ным, и INT отбрасывает дробную часть, то нам потребуются строки такие
как
q1 := INT(s2/b);
IF (q1 > s2/b) THEN q1:= q1 – 1;
s2:= s2 – b*q1.
Проверьте Вашу программу нахождением обратного числа по модулю,
что можно проделать вручную или, используя знание, что 27
–1
≡ 104 (mod 2807);
19
–1
≡ 104 (mod 1652).
2. Напишите программы для решения уравнений
ax + by = d, и ax +
+ by+cz = d
. Используйте программы для решения уравнений, приведенных
ранее.
3.14. Проект: ax + by для x и y – неотрицательных. Пусть a > 0, b > 0
и (
a, b) = 1. Мы исследуем ряд чисел А = {ax + by: x ≥ 0 и y ≥ 0}. Покажите,
что если
m ∈ A, то ab – a – m ∉ A. Дадим два намёка; первый из них подобен
второму, но немного проще. Так как (
a, b) = 1, мы можем найти целые чис-
ла
x, y такие, что ax + by = m ; также для некоторого k ∈ Z, a(x + kb) +
+
b(x – ka) = m; почему это означает, что мы можем выбрать x таким, что
0
≤ x ≤ b – 1? Теперь предположим (для противоречия), что m и ab – a – b –
– m
оба не принадлежат А: тогда существуют целые числа x, y, u, v такие,
что
ax + by = m , 0 ≤ x ≤ b – 1, y < 0 (или m ∈ A), и au + bv = ab – a – b – m ,
0
≤ u ≤ b – 1, v < 0. Докажите, что a( x + u + 1) + b( y + v + 1) = ab и исполь-
зуйте (
a, b) = 1, чтобы доказать y + v + 1 = la, x + u + 1 = (1– l )b для неко-
торого целого
l. Теперь мы совсем недалеко от требуемого противоречия!
Докажите, что все числа
m > ab – a – b находятся в А и только поло-
вина чисел
m для 0 ≤ m ≤ ab – a – b находятся в А. Напишите программу для
определения (для данных взаимно простых чисел
a и b), какие числа m
должны принадлежать
А.

Страницы