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

Расширенный алгоритм Евклида — это расширение алгоритма Евклида, которое вычисляет кроме наибольшего общего делителя (НОД) целых чисел a и b ещё и коэффициенты соотношения Безу, то есть целые x и y, такие что Алгоритм является , поскольку НОД является единственным числом, которое одновременно удовлетворяет уравнению и делит входные числа. Алгоритм позволяет также почти без дополнительных затрат вычислять частные от деления a и b на их наибольший общий делитель. Под Расширенным алгоритмом Евклида также понимается для вычисления и вычисления коэффициентов соотношения Безу двух многочленов от одной переменной. Расширенный алгоритм Евклида особенно полезен, когда a и b взаимно просты. При таких условиях x является модульным обратным числа a по модулю b, а y является модульным обратным числа b по модулю a. Аналогично, расширенный алгоритм Евклида для многочленов позволяет вычислить обратное число в алгебраических расширениях и, в частности, в конечных полях непростого порядка. Поэтому оба расширенных алгоритма Евклида широко используются в криптографии. В частности, вычисление обратного элемента по модулю является существенным шагом в получении пары ключей в методе RSA шифрования с открытым ключом.