extended Euclidean algorithm

extended Euclidean algorithm
Name	Extended Euclidean algorithm
Inventors	Euclid
Year	300 BC
Field	Mathematics
Inputs	two integers
Outputs	greatest common divisor and coefficients

extended Euclidean algorithm The extended Euclidean algorithm is a classical procedure originating with Euclid for computing the greatest common divisor of two integers and producing integers that express that gcd as a linear combination of the inputs. It refines the Euclidean algorithm by tracing the sequence of quotients to yield Bézout coefficients, enabling solutions to linear Diophantine equations, inverse computations in modular arithmetic, and constructions in algebraic number theory. The method underlies algorithms used in RSA algorithm, Diffie–Hellman key exchange, and computational systems developed at institutions like MIT and Bell Labs.

Definition and purpose

The algorithm takes two integers a and b and returns gcd(a,b) together with integers x and y satisfying ax + by = gcd(a,b). Its purpose includes computing multiplicative inverses modulo n for use in RSA algorithm and protocols by Whitfield Diffie, solving linear congruences in contexts like Fermat-related proofs, and providing foundational steps in algorithms employed at IBM and Intel for cryptographic primitives. Historically, its role appears in works associated with Euclid and was later formalized in computational settings by researchers at Princeton University and University of Cambridge.

Algorithm description

The algorithm iteratively applies division with remainder as in the Euclidean algorithm while maintaining auxiliary linear combinations. Starting with pairs (r0, r1) = (a, b) and coefficients (s0, s1) = (1, 0), (t0, t1) = (0, 1), each step computes a quotient q = ⌊r0 / r1⌋ and updates (r0, r1) ← (r1, r0 − q r1) and (s0, s1) ← (s1, s0 − q s1), (t0, t1) ← (t1, t0 − q t1). When r1 becomes zero, r0 = gcd(a,b) and s0, t0 are the Bézout coefficients. This iterative structure parallels algorithms implemented in libraries at GNU Project, Microsoft Research, and in number-theoretic software such as SageMath and PARI/GP.

Correctness and complexity

Correctness follows from invariants preserving linear combinations: at each iteration ri = ai a + bi b for integers ai, bi, a fact used in proofs by mathematicians at University of Oxford and in textbooks from Cambridge University Press. Termination is guaranteed by the strictly decreasing nonnegative remainders, a property studied in the context of Diophantus-era arithmetic and modern analysis at institutions like ETH Zurich. Time complexity on a Turing machine for integers of bit-length n is O(n^2) for the classical implementation and can be improved to subquadratic using fast division techniques developed at Bell Labs and in research by Peter L. Montgomery and groups at Stanford University. Worst-case input pairs relate to consecutive Fibonacci numbers, a connection noted in work by Lamé.

Applications

Key applications include computing modular inverses used in RSA algorithm key generation and signing, solving linear Diophantine equations as in algorithms from Princeton University courses, and polynomial analogues used in coding theory developed at Bell Labs and AT&T. It is essential in lattice basis computations appearing in research at École Polytechnique Fédérale de Lausanne and in algorithms for algebraic number fields used by researchers at Harvard University. Implementations support cryptographic protocols standardized by organizations such as IETF and NIST and are used in educational software from Wolfram Research.

Examples

For a = 240 and b = 46, the algorithm produces gcd 2 with Bézout coefficients x = −9 and y = 47, yielding 240(−9) + 46(47) = 2; this calculation is commonly taught in courses at Massachusetts Institute of Technology and illustrated in texts by G. H. Hardy and E. M. Wright. Another canonical example uses consecutive Fibonacci numbers F_k and F_{k+1}, which attain worst-case iteration counts studied by S. Ramanujan and later authors at Princeton University.

Variants and implementations

Variants include the binary extended Euclidean algorithm (Stein's algorithm) attributed to J. Stein, which replaces division by shifts and subtraction and is favored in implementations on hardware by Intel and ARM Holdings. Subquadratic variants use divide-and-conquer strategies influenced by work at Bell Labs and asymptotically faster multiplication algorithms by researchers at Google and Microsoft Research. Implementations appear in standard libraries such as those produced by the GNU Project, in computer algebra systems like SageMath and Mathematica from Wolfram Research, and in cryptographic toolkits maintained by OpenSSL Project.

Category:Number theory