Extended Euclidean algorithm
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.
- Comment
- enIn 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.
- Has abstract
- enIn 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. Extended Euclidean algorithm 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.
- Is primary topic of
- Extended Euclidean algorithm
- Label
- enExtended Euclidean algorithm
- Link from a Wikipage to an external page
- mathforum.org/library/drmath/view/51675.html
- Link from a Wikipage to another Wikipage
- Additive inverse
- Algebraic field extension
- Arithmetic
- Bézout's identity
- Bijective
- Category:Articles with example pseudocode
- Category:Euclid
- Category:Number theoretic algorithms
- Certifying algorithm
- Charles E. Leiserson
- Clifford Stein
- Coding theory
- Computer algebra
- Computer program
- Computer programming
- Content (algebra)
- Coprime
- Cryptography
- Euclid's lemma
- Euclidean algorithm
- Euclidean division
- Euclidean division of polynomials
- Euclidean domain
- Field (mathematics)
- Finite field
- Finite field arithmetic
- Greatest common divisor
- Integer overflow
- Integral part
- Introduction to Algorithms
- Irreducible polynomial
- Kuṭṭaka
- Leading coefficient
- Linear congruence theorem
- Modular arithmetic
- Modular multiplicative inverse
- Monic polynomial
- Multiplicative inverse
- nZ
- Parallel assignment
- Polynomial greatest common divisor
- Prime field
- Prime number
- Primitive polynomial (ring theory)
- Quotient ring
- Resultant
- Ronald L. Rivest
- RSA (algorithm)
- Simple extension
- Subresultant
- The Art of Computer Programming
- Thomas H. Cormen
- Unit (ring theory)
- Univariate polynomial
- SameAs
- Algorisme d'Euclides ampliat
- Algorithme d'Euclide étendu
- Algoritmo de Euclides estendido
- Algoritmo esteso di Euclide
- Erweiterter euklidischer Algorithmus
- Extended Euclidean algorithm
- Giải thuật Euclid mở rộng
- Išplėstinis Euklido algoritmas
- m.0pd13
- NF4m
- Q1362750
- Razširjeni Evklidov algoritem
- Rozšířený Eukleidův algoritmus
- Rozšírený Euklidov algoritmus
- Uitgebreid algoritme van Euclides
- Проширени Еуклидов алгоритам
- Расширенный алгоритм Евклида
- Розширений алгоритм Евкліда
- الگوریتم تعمیمیافته اقلیدس
- خوارزمية إقليدس الممددة
- 扩展欧几里得算法
- SeeAlso
- Extended GCD algorithm
- Polynomial greatest common divisor
- Subject
- Category:Articles with example pseudocode
- Category:Euclid
- Category:Number theoretic algorithms
- WasDerivedFrom
- Extended Euclidean algorithm?oldid=1113184203&ns=0
- WikiPageLength
- 28045
- Wikipage page ID
- 99438
- Wikipage revision ID
- 1113184203
- WikiPageUsesTemplate
- Template:!
- Template:Blue
- Template:Brown
- Template:Cite book
- Template:Cyan
- Template:Em
- Template:Green
- Template:Hatnote
- Template:ISBN
- Template:Magenta
- Template:Main
- Template:Math
- Template:Mvar
- Template:Number theoretic algorithms
- Template:Olive
- Template:Red
- Template:See also
- Template:Sfrac
- Template:Short description
- Template:Void
- Template:Wikibooks