Отношение a / b допускает представление в виде цепной дроби:
.
При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t / s, взятому со знаком минус:
.
Последовательность равенств, задающая алгоритм Евклида может быть переписана в форме
Последнее слагаемое в правой части равенства всегда равно обратному значению левой части следующего уравнения. Поэтому первые два уравнения могут быть объедены в форме
Третье равенство может быть использовано чтобы заменить знаменатель выражения r 1/ r 0, получим
Последнее отношение остатков rk / rk −1 всегда может быть заменено используя следующее равенство в последовательности, и так до последнего уравнения. Результатом является цепная дробь
В приведённом выше примере, НОД(1071, 462) было посчитано и были найдены частные qk 2,3 и 7 соответственно. Поэтому, 1071/462 может быть записана как
Литература
- Салома А. Криптография с открытым ключом. — М.: Мир, 1995. — 318 с. — ISBN 5-03-001991-X.
- Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
- Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии. – М.: Горячая линия. Телеком, 2001. – 120с.
4. Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. и др. Кодирование информации (двоичные коды). / Под ред. Н.Т. Березюка. – Харьков: Вища школа, 1978. – 252 с.
|
|
4. Блейхут Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986.
5. Брейсуэлл Р. Преобразование Хартли. / Пер. с английского А.И. Папкова. – М.: Мир, 1990. – 175с.
6. Борисов В.А., Калмыков В.В., Ковальчук Я.М. и др. Радиотехнические системы передачи информации. / Под ред. В.В. Калмыкова. – М.: Радио и связи, 1990. – 304с.