Un algorithme permettant de déterminer le plus grand commun diviseur (PGCD) de deux entiers sans connaître leur factorisation. - Euclide (-300 bc) / Algorithm

see also

• Greatest common divisor, the extended Euclidean algorithm, and speed!
  • Binary GCD
  • Fastest way to compute the greatest common divisor
• Faster practical modular inversion - given a remainder $a$ and a modulus $m$, find $x$ such that $a⋅x \mod m=1$

# pseudo code ⮺

function gcd(a, b)
    while b ≠ 0
       t := b; 
       b := a mod b; 
       a := t; 
    return a;

or

function gcd(a, b)
    if b = 0
       return a; 
    else
       return gcd(b, a mod b);

# Lemme d’Euclide ⮺