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.
BCH codeBinary GCD algorithmBinary Goppa codeBlum–Goldwasser cryptosystemBézout's identityCertifying algorithmChinese remainder theoremDigital Signature AlgorithmDiscrete logarithmEEAElGamal encryptionEuclidEuclideanEuclidean algorithmEuclidean domainExtended Euclid's algorithmExtended Euclidean AlgorithmExtended GCDExtended euclidean algorithmFermat's little theoremFinite fieldFinite field arithmeticGreatest common divisorGuarded Command LanguageImaginary hyperelliptic curveKuṭṭakaLenstra elliptic-curve factorizationLinear equation over a ringList of algorithmsList of number theory topicsList of terms relating to algorithms and data structuresList of things named after EuclidMerkle–Hellman knapsack cryptosystemModular arithmeticModular exponentiationModular multiplicative inverseMontgomery modular multiplicationMultiplicative inverseOkamoto–Uchiyama cryptosystemP-complete
Link from a Wikipage to another Wikipage
primaryTopic
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.
has abstract
En mathématiques, l'algorithme ...... de rupture, corps finis, etc.
@fr
Het uitgebreide algoritme van ...... het algoritme tot stand komt.
@nl
In arithmetic and computer pro ...... public-key encryption method.
@en
In aritmetica e nella programm ...... poi da Eulero intorno al 1731.
@it
L'algorisme d'Euclides ampliat ...... bres a la identitat de Bézout.
@ca
O Algoritmo de Euclides estend ...... do método de encriptação RSA.
@pt
Rozšířený Eukleidův algoritmus ...... sel jejich lineární kombinací.
@cs
Розширений алгоритм Евкліда —ц ...... обернене щодо b за модулем a.
@uk
في الحسابيات وفي برمجة الحاسوب ...... اللذين يظهران في متطابقة بوزو.
@ar
扩展欧几里得算法（英語：Extended Euclidean ...... 求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。
@zh
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,003,613,686
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
type
comment
En mathématiques, l'algorithme ...... cilement la solution générale.
@fr
Het uitgebreide algoritme van ...... e lineaire combinatie van en .
@nl
In arithmetic and computer pro ...... their greatest common divisor.
@en
In aritmetica e nella programm ...... moltiplicativo di b modulo a.
@it
L'algorisme d'Euclides ampliat ...... bres a la identitat de Bézout.
@ca
O Algoritmo de Euclides estend ...... do método de encriptação RSA.
@pt
Rozšířený Eukleidův algoritmus ...... sel jejich lineární kombinací.
@cs
Розширений алгоритм Евкліда —ц ...... обернене щодо b за модулем a.
@uk
في الحسابيات وفي برمجة الحاسوب ...... اللذين يظهران في متطابقة بوزو.
@ar
扩展欧几里得算法（英語：Extended Euclidean ...... 求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。
@zh
label
Algorisme d'Euclides ampliat
@ca
Algorithme d'Euclide étendu
@fr
Algoritmo de Euclides estendido
@pt
Algoritmo esteso di Euclide
@it
Erweiterter euklidischer Algorithmus
@de
Extended Euclidean algorithm
@en
Rozšířený Eukleidův algoritmus
@cs
Uitgebreid algoritme van Euclides
@nl
Розширений алгоритм Евкліда
@uk
خوارزمية إقليدس الممددة
@ar