Расширенный алгоритм Евклида и соотношение Безу

Основная статья: Соотношение Безу

Формулы для r_i могут быть переписаны следующим образом:

r₁ = a + b( − q₀)

r₂ = b − r₁q₁ = a( − q₁) + b(1 + q₁q₀)

НОД (a,b) = r_n = as + bt

здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t —коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

Связь с цепными дробями

Отношение a / b допускает представление в виде цепной дроби:

.

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t / s, взятому со знаком минус:

.

Последовательность равенств, задающая алгоритм Евклида может быть переписана в форме

Последнее слагаемое в правой части равенства всегда равно обратному значению левой части следующего уравнения. Поэтому первые два уравнения могут быть объедены в форме

Третье равенство может быть использовано чтобы заменить знаменатель выражения r₁/r₀, получим

Последнее отношение остатков r_k/r_k−1 всегда может быть заменено используя следующее равенство в последовательности, и так до последнего уравнения. Результатом является цепная дробь

В приведённом выше примере, НОД(1071, 462) было посчитано и были найдены частные q_k 2,3 и 7 соответственно. Поэтому, 1071/462 может быть записана как

Литература

1. Салома А. Криптография с открытым ключом. — М.: Мир, 1995. — 318 с. — ISBN 5-03-001991-X.

2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.

3. Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии. – М.: Горячая линия. Телеком, 2001. – 120с.

4. Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. и др. Кодирование информации (двоичные коды). / Под ред. Н.Т. Березюка. – Харьков: Вища школа, 1978. – 252 с.

4. Блейхут Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986.

5. Брейсуэлл Р. Преобразование Хартли. / Пер. с английского А.И. Папкова. – М.: Мир, 1990. – 175с.

6. Борисов В.А., Калмыков В.В., Ковальчук Я.М. и др. Радиотехнические системы передачи информации. / Под ред. В.В. Калмыкова. – М.: Радио и связи, 1990. – 304с.

14