Extended Euclidean algorithm: Difference between revisions

From Elliptic Curve Crypto
cat, ref
→‎Using GNU multiprecision bignum classes: spell out words & skip the branding
 
(5 intermediate revisions by the same user not shown)
Line 3: Line 3:
[[Category:Number theory]]
[[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]]
The objective of the '''extended Euclidean algorithm''' is to compute the greatest common divisor of two natural numbers and solve [[Bézout’s identity]]


:<math>ax+by=d</math>.
:<math>ax+by=d</math>.
Line 9: Line 9:
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>.
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
If <math>d=1</math>, the algorithm yields the [[modular 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>
:<math>ax\equiv 1 \mod b</math>
Line 15: Line 15:
:<math>by \equiv 1\mod a</math>
:<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].
are solved.
== Example code ==
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="">
#include <iostream>
#include <iostream>
#include <cassert>
#include <cassert>


int main(int argc, char **argv) {
int main(int argc, char **argv) {
     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,
     std::cout << "Enter two integers: ";
        s0 = 1, s1, s = 0, t0 = 0, t1, t = 1;
     std::cout << "Enter two positive integers: ";
     std::cin >> a >> b;
     std::cin >> a >> b;
     assert(a > 0 && b > 0); r0=a; r=b;
     assert(a > 0 && b > 0); r0=a; r=b;
     while(r>0) {
     while(r != 0) {
         q=r0/r;
         q = r0 / r;
         r1=r0-q*r; r0=r; r=r1;
         r1 = r0 - q * r; r0 = r; r = r1;
         s1=s0-q*s; s0=s; s=s1;
         s1 = s0 - q * s; s0 = s; s = s1;
         t1=t0-q*t; t0=t; t=t1;
         t1 = t0 - q * t; t0 = t; t = t1;
     }
     }
     std::cout
     std::cout
Line 42: Line 45:
}
}


</syntaxhighlight>
== Using multiple precision big number classes ==
The <tt>long int</tt> primitive data type in C++ cannot handle numbers bigger than 18,446,744,073,709,551,615 on most computers.
The program above may be adapted to handle much, much bigger numbers with multiple precision arithmetic, and this is practical for actual implementations that will be highly efficient.  Be sure <tt>g++</tt>, <tt>gmp</tt>, <tt>gmp++</tt>, <tt>gmp-devel</tt> are installed on your your Fedora Linux system, e.g.
<syntaxhighlight lang="bash">
$ sudo dnf install gmp gmp++ gmp-devel
</syntaxhighlight>
Be sure you have
<syntaxhighlight lang="cpp">
#include <gmpxx.h>
</syntaxhighlight>
along with the other includes, declare the variables as <tt>mpz_class</tt> instead of <tt>long int</tt>, and link the GMP Bignum libraries when you compile <ref>The GNU Multiple Precision Arithmetic Library. https://gmplib.org/</ref><ref>— , Manual § 12.1 C++ Interface General. https://gmplib.org/manual/C_002b_002b-Interface-General</ref>, assuming here you have saved the program as <tt>e-euclid.cpp</tt>.
<syntaxhighlight lang="bash">
$ g++ -o e-euclid e-euclid.cpp -lgmpxx -lgmp
$ ./e-euclid
</syntaxhighlight>
</syntaxhighlight>

Latest revision as of 06:57, 23 December 2024


The objective of the extended Euclidean algorithm is to compute the greatest common divisor 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 inverses [1] of a mod b and b mod a since in this case the congruences

and

are solved.

Example code

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 positive 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;
}

Using multiple precision big number classes

The long int primitive data type in C++ cannot handle numbers bigger than 18,446,744,073,709,551,615 on most computers. The program above may be adapted to handle much, much bigger numbers with multiple precision arithmetic, and this is practical for actual implementations that will be highly efficient. Be sure g++, gmp, gmp++, gmp-devel are installed on your your Fedora Linux system, e.g.

$ sudo dnf install gmp gmp++ gmp-devel

Be sure you have

#include <gmpxx.h>

along with the other includes, declare the variables as mpz_class instead of long int, and link the GMP Bignum libraries when you compile [2][3], assuming here you have saved the program as e-euclid.cpp.

$ g++ -o e-euclid e-euclid.cpp -lgmpxx -lgmp
$ ./e-euclid
  1. 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
  2. The GNU Multiple Precision Arithmetic Library. https://gmplib.org/
  3. — , Manual § 12.1 C++ Interface General. https://gmplib.org/manual/C_002b_002b-Interface-General