AlgoScope

Extended Euclid

algorithmintermediateTime O(log min(a, b))Space O(log min(a, b))

Euclid's algorithm finds the gcd by repeated division: replace the pair (a, b) with (b, a mod b) until the remainder is zero. The extended version keeps the receipts. Each division a = q b + r can be turned around into r = a - q b, so once the bottom row expresses the gcd in terms of its own a and b, every row above can express it in terms of its a and b too, by swapping the coefficients and subtracting q times one of them. At the top you get integers x and y with a x + b y = gcd, which is how modular inverses are computed.

abqrxy012

Find gcd(48, 18) and, on the way back, integers x and y with 48 x + 18 y = gcd. Each row divides: a = q b + r, and the next row starts from (b, r). The remainders shrink, so the table is short.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. Row 0 divides 48 by 18. What is the remainder?

    • 11
    • 12
    • 13

    Answer: 12. 48 = 2 x 18 + 12.

  2. Row 1 divides 18 by 12. What is the remainder?

    • 5
    • 6
    • 7

    Answer: 6. 18 = 1 x 12 + 6.

  3. Row 2 divides 12 by 6. What is the remainder?

    • 0
    • 1
    • 5

    Answer: 0. 12 = 2 x 6 + 0.

How it runs, step by step

  1. Find gcd(48, 18) and, on the way back, integers x and y with 48 x + 18 y = gcd. Each row divides: a = q b + r, and the next row starts from (b, r). The remainders shrink, so the table is short.

    Extended Euclid on 48 and 18.

  2. Row 0: 48 = 2 x 18 + 12. Next row: a = 18, b = 12, the divisor and the remainder.

    Row 0: 48 equals 2 times 18 plus 12.

  3. Row 1: 18 = 1 x 12 + 6. Next row: a = 12, b = 6, the divisor and the remainder.

    Row 1: 18 equals 1 times 12 plus 6.

  4. Row 2: 12 = 2 x 6 + 0. The remainder is 0, so the divisor 6 is the gcd. Now climb back up carrying coefficients.

    Row 2: 12 equals 2 times 6 plus 0.

  5. Bottom row: 6 is the gcd itself, so 12 x 0 + 6 x 1 = 6. Start with x = 0, y = 1.

    Row 2: x 0, y 1.

  6. Row 1 from the row below, where b x 0 + r x 1 = 6. Since r = a - q b, swap and subtract: x = 1 and y = 0 - 1 x 1 = -1. Check: 18 x 1 + 12 x -1 = 6.

    Row 1: x 1, y -1.

  7. Row 0 from the row below, where b x 1 + r x -1 = 6. Since r = a - q b, swap and subtract: x = -1 and y = 1 - 2 x -1 = 3. Check: 48 x -1 + 18 x 3 = 6.

    Row 0: x -1, y 3.

  8. gcd(48, 18) = 6 and 48 x -1 + 18 x 3 = 6, Bezout's identity. The gcd is not 1, so 48 has no inverse modulo 18. Any common divisor divides both sides.

    gcd 6 with coefficients -1 and 3.

Remember

  • Down: a = q b + r, then continue with (b, r). The last non-zero remainder is the gcd.
  • Up: from b x' + r y' = g and r = a - q b, the row above has x = y' and y = x' - q y'.
  • If gcd(a, m) = 1, the x in a x + m y = 1 is the inverse of a modulo m.

Topics covered

Related

Where this is used

SecurityRSA private keys

A key pair is not finished until you have the private exponent d, the number with e * d = 1 modulo lcm(p-1, q-1). That d is precisely the x extended Euclid returns for that pair, and there is nothing to search: the modulus is a 2048-bit number, but with the usual e = 65537 the first division drops the pair below 65537 and a couple of dozen steps finish it. OpenSSL does this once during key generation, in BN_mod_inverse.

CompilersDividing by a constant without a divide

When a compiler can prove a division is exact, it emits a multiply instead. Pointer subtraction is the everyday case: the byte gap is always a multiple of the element size, so LLVM and GCC multiply by the inverse of that size modulo 2^32 or 2^64, which is a Bezout coefficient worked out at build time. An integer divide costs tens of cycles on current x86 and the multiply costs three.

Error correctionReed-Solomon decoding in QR codes

Repairing a scratched QR code means finding two polynomials, an error locator and an error evaluator, that satisfy a congruence modulo x^2t. Run extended Euclid on x^2t and the syndrome polynomial and stop halfway, as soon as the remainder drops below degree t, and it hands you both: the remainder is the evaluator and the accumulated coefficient is the locator. ZXing, the open source barcode library, decodes this way in its runEuclideanAlgorithm routine. Polynomials support division with remainder just as integers do, so the algorithm needs no change at all.

CryptographyConstant-time inverses in libsecp256k1

Signing an ECDSA transaction inverts the secret nonce modulo the curve order, and verifying one inverts s. The textbook loop leaks that secret through timing, because the number of divisions and the branch taken at each step both depend on the value. Bitcoin Core's libsecp256k1 uses safegcd, a Bernstein-Yang rearrangement of extended Euclid that runs a fixed number of iterations with no data-dependent branches, and it beats the exponentiation trick it replaced.

Why it works this way

The x you get back is often negative

Run the algorithm on 17 and 43 and you get 17 * (-5) + 43 * 2 = 1. That -5 is a correct coefficient but not a usable inverse; the answer you want is 38, which is -5 + 43. Normalise with ((x % m) + m) % m, because % on a negative value returns a negative in Kotlin, Java, C and JavaScript. Python is the exception and already gives 38.

The algorithm returns an x even when no inverse exists

It never fails, so it is tempting to use x without looking at g. If g is bigger than 1 there is no inverse at all: 2 has no inverse modulo 4, because 2 times anything is even and the even values modulo 4 are 0 and 2, never 1. Check g first and treat anything above 1 as no answer. This is why RSA key generation requires e to be coprime to lcm(p-1, q-1), and retries with fresh primes when it is not.

The pair (x, y) is one of infinitely many

If a x + b y = g then so does (x + k b/g, y - k a/g) for every integer k, since the two added terms cancel. This version returns the small pair: |x| stays at or below b/(2g) and |y| at or below a/(2g). The one exception is a = b, where it returns x = 0 and y = 1. That bound is worth knowing, because it means the coefficients themselves cannot overflow when a and b fit. The product a * x can overflow, so check the identity in a wider type than you solved it in.

The slow case is consecutive Fibonacci numbers

Every quotient in gcd(55, 34) is 1 until the final step, so each division subtracts the smaller number exactly once and the pair shrinks as slowly as it is able to. Fibonacci pairs are the worst input at any size, which is Lame's theorem: the number of divisions never exceeds about five times the count of decimal digits in the smaller number. Two 64-bit inputs are therefore a hundred steps at most, which is why nobody puts a guard on this loop.

Read more

Next up