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

---

Расширенный алгоритм Евклида — модификация алгоритма Евклида, вычисляющая, кроме наибольшего общего делителя (НОД) целых чисел ${\displaystyle a}$ и ${\displaystyle b}$, ещё и коэффициенты соотношения Безу, то есть такие целые ${\displaystyle x}$ и ${\displaystyle y}$, что

Алгоритм является удостоверяющим^[en], то есть помимо решения задачи приводит также доказательство корректности этого решения. Это связано с тем, что НОД является единственным числом, которое одновременно удовлетворяет уравнению и делит входные числа. Алгоритм позволяет также почти без дополнительных затрат вычислять частные от деления ${\displaystyle a}$ и ${\displaystyle b}$ на их наибольший общий делитель.

Под расширенным алгоритмом Евклида также понимается очень похожий алгоритм^[en] для вычисления наибольшего общего делителя многочленов и вычисления коэффициентов соотношения Безу двух многочленов от одной переменной.

Когда ${\displaystyle a}$ и ${\displaystyle b}$ взаимно просты, получаемый расширенным алгоритмом Евклида ${\displaystyle x}$ является модульным обратным числа ${\displaystyle a}$ по модулю ${\displaystyle b}$, а ${\displaystyle y}$ является модульным обратным числа ${\displaystyle b}$ по модулю ${\displaystyle a}$. Аналогично, расширенный алгоритм Евклида для многочленов позволяет вычислить обратное число в алгебраических расширениях и, в частности, в конечных полях непростого порядка. Поэтому оба расширенных алгоритма Евклида широко используются в криптографии. В частности, вычисление обратного элемента по модулю является существенным шагом в получении пары ключей в методе RSA шифрования с открытым ключом.

---