Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Extended Euclidean algorithm
Summary
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that
This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs.
It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor.
also refers to a very similar algorithm for computing the polynomial greatest common divisor and the coefficients of Bézout's identity of two univariate polynomials.
The extended Euclidean algorithm is particularly useful when a and b are coprime. With that provision, x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Similarly, the polynomial extended Euclidean algorithm allows one to compute the multiplicative inverse in algebraic field extensions and, in particular in finite fields of non prime order. It follows that both extended Euclidean algorithms are widely used in cryptography. In particular, the computation of the modular multiplicative inverse is an essential step in the derivation of key-pairs in the RSA public-key encryption method.
The standard Euclidean algorithm proceeds by a succession of Euclidean divisions whose quotients are not used. Only the remainders are kept. For the extended algorithm, the successive quotients are used. More precisely, the standard Euclidean algorithm with a and b as input, consists of computing a sequence of quotients and a sequence of remainders such that
It is the main property of Euclidean division that the inequalities on the right define uniquely and from and
The computation stops when one reaches a remainder which is zero; the greatest common divisor is then the last non zero remainder
The extended Euclidean algorithm proceeds similarly, but adds two other sequences, as follows
The computation also stops when and gives
is the greatest common divisor of the input and
The Bézout coefficients are and that is
The quotients of a and b by their greatest common divisor are given by and
Moreover, if a and b are both positive and , then
for where denotes the integral part of x, that is the greatest integer not greater than x.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.