Extended Euclidean Algorithm

The extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y (one of which is typically negative) that satisfy Bézout's identity

The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the multiplicative inverse of a modulo b, and y is the multiplicative inverse of b modulo a.

Read more about Extended Euclidean AlgorithmInformal Formulation of The Algorithm, Computing A Multiplicative Inverse in A Finite Field, The Case of More Than Two Numbers

Other articles related to "algorithm, extended euclidean algorithm":

Imaginary Hyperelliptic Curve - The Jacobian of A Hyperelliptic Curve - Cantor's Algorithm
... There is an algorithm which takes two reduced divisors and in their Mumford representation and produces the unique reduced divisor, again in its Mumford representation, such that is equivalent to ... of the Jacobian can be represented by the one reduced divisor it contains, the algorithm allows to perform the group operation on these reduced divisors given in their Mumford representation ... The algorithm was originally developed by David G ...
Extended Euclidean Algorithm - The Case of More Than Two Numbers
... So if then there are and such that so the final equation will be So then to apply to n numbers we use induction with the equations following directly. ...
Modular Multiplicative Inverse - Computation - Extended Euclidean Algorithm
... inverse of a modulo m can be found with the extended Euclidean algorithm ... The algorithm finds solutions to Bézout's identity where a and b are given and x, y and gcd(a, b) are the integers that the algorithm discovers ... This is the exact form of equation that the extended Euclidean algorithm solves—the only difference being that gcd(a, m) = 1 is predetermined instead of discovered ...

Famous quotes containing the word extended:

    Whenever there are in any country uncultivated lands and unemployed poor, it is clear that the laws of property have been so far extended as to violate natural right. The earth is given as a common stock for man to labor and live on.... The small landowners are the most precious part of a state.
    Thomas Jefferson (1743–1826)