Extended Euclidean algorithm: Difference between revisions

From Elliptic Curve Crypto
m example program
spacing for readability in program
Line 22: Line 22:


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,
        s0 = 1, s1, s = 0, t0 = 0, t1, t = 1;
     std::cout << "Enter two positive integers: ";
     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

Revision as of 19:45, 20 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 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 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;
}
  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