Extended Euclidean algorithm: Difference between revisions
From Elliptic Curve Crypto
pseudocode |
cat, ref |
||
Line 1: | Line 1: | ||
The objective of the ''' | [[Category:Algorithms]] | ||
[[Category:C++ programs]] | |||
[[Category:Number theory]] | |||
The objective of the '''extended Euclidean algorithm''' is to compute the greatest common denominator of two natural numbers and solve [[Bézout’s identity]] | |||
:<math>ax+by=d</math>. | |||
Given two positive integers ''a'' and ''b'', this [[Diophantine equation]] is solved for integers ''x, y'', which will not both be positive, and <math>d=\gcd(a,b)</math>. | |||
If <math>d=1</math>, the algorithm yields the [[modular multiplicative inverse]]s<ref>Bufalo, Michele, Daniele Bufalo, and Giuseppe Orlando. “A Note on the Computation of the Modular Inverse for Cryptography” ''Axioms,'' vol. 10, no. 2(116), 2021. https://www.mdpi.com/2075-1680/10/2/116</ref> of ''a'' mod ''b'' and ''b'' mod ''a'' since in this case the congruences | |||
:<math>ax\equiv 1 \mod b</math> | |||
and | |||
:<math>by \equiv 1\mod a</math> | |||
are solved. Here is a naïve C++ implementation of [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode pseudocode found on Wikipedia]. | |||
<syntaxhighlight lang="cpp" line> | <syntaxhighlight lang="cpp" line> | ||
Line 8: | Line 24: | ||
long int a,b,q,r0,r1,r,s0=1,s1,s=0,t0=0,t1,t=1; | long int a,b,q,r0,r1,r,s0=1,s1,s=0,t0=0,t1,t=1; | ||
std::cout << "Enter two integers: "; | std::cout << "Enter two integers: "; | ||
std::cin >> a >> b; assert(a > 0 && b > 0); | std::cin >> a >> b; | ||
assert(a > 0 && b > 0); r0=a; r=b; | |||
while(r>0) { | while(r>0) { | ||
q=r0/r; | q=r0/r; | ||
Line 17: | Line 33: | ||
} | } | ||
std::cout | std::cout | ||
<< "Bézout coefficients: " << s0 << ", " << t0 << std::endl | << "Bézout coefficients: " | ||
<< "greatest common divisor: " << r0 << std::endl | << s0 << ", " << t0 << std::endl | ||
<< "quotients by the gcd: " << t << ", "<< s << std::endl; | << "greatest common divisor: " | ||
<< r0 << std::endl | |||
<< "quotients by the gcd: " | |||
<< t << ", "<< s << std::endl; | |||
return 0; | return 0; | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> |
Revision as of 19:16, 20 December 2024
The objective of the extended Euclidean algorithm is to compute the greatest common denominator of two natural numbers and solve Bézout’s identity
- .
Given two positive integers a and b, this Diophantine equation is solved for integers x, y, which will not both be positive, and .
If , the algorithm yields the modular multiplicative inverses[1] of a mod b and b mod a since in this case the congruences
and
are solved. Here is a naïve C++ implementation of pseudocode found on Wikipedia.
#include <iostream>
#include <cassert>
int main(int argc, char **argv) {
long int a,b,q,r0,r1,r,s0=1,s1,s=0,t0=0,t1,t=1;
std::cout << "Enter two integers: ";
std::cin >> a >> b;
assert(a > 0 && b > 0); r0=a; r=b;
while(r>0) {
q=r0/r;
r1=r0-q*r; r0=r; r=r1;
s1=s0-q*s; s0=s; s=s1;
t1=t0-q*t; t0=t; t=t1;
}
std::cout
<< "Bézout coefficients: "
<< s0 << ", " << t0 << std::endl
<< "greatest common divisor: "
<< r0 << std::endl
<< "quotients by the gcd: "
<< t << ", "<< s << std::endl;
return 0;
}
- ↑ Bufalo, Michele, Daniele Bufalo, and Giuseppe Orlando. “A Note on the Computation of the Modular Inverse for Cryptography” Axioms, vol. 10, no. 2(116), 2021. https://www.mdpi.com/2075-1680/10/2/116