Extended Euclidean algorithm: Difference between revisions

From Elliptic Curve Crypto
with bignum arithmetic
→‎Using GNU multiprecision bignum classes: spell out words & skip the branding
 
Line 47: Line 47:
</syntaxhighlight>
</syntaxhighlight>


== Using GNU multiprecision bignum classes ==
== Using multiple precision big number classes ==


The <tt>long int</tt> primitive type in C++ cannot handle numbers bigger than 18,446,744,073,709,551,615 on most computers.
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 multiprecision 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.
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">
<syntaxhighlight lang="bash">
$ sudo dnf install gmp gmp++ gmp-devel
$ sudo dnf install gmp gmp++ gmp-devel
Line 58: Line 58:
#include <gmpxx.h>
#include <gmpxx.h>
</syntaxhighlight>
</syntaxhighlight>
along with the other includes, declare the variables as <tt>mpz_class</tt> instead of <tt>long int</tt>, and link the 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>.
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">
<syntaxhighlight lang="bash">
$ g++ -o e-euclid e-euclid.cpp -lgmpxx -lgmp
$ g++ -o e-euclid e-euclid.cpp -lgmpxx -lgmp
$ ./e-euclid
$ ./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