Введение

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

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

Вычисление инверсов умножения в модульных структурах

Расширенный алгоритм Евклида — основной инструмент для вычисления мультипликативных инверсов в модульных структурах, таких как модульные целые числа и алгебраические расширения полей. Примечательным примером последнего являются конечные поля непороскового порядка.