GCD/LCM Overflow — RSA Signatures Fail 0.1% of Keys

The Euclidean algorithm is 2300 years old, appears in Euclid's Elements (Book VII, Proposition 2), and is still one of the fastest algorithms relative to input size that exists. For 64-bit numbers, it terminates in at most 93 steps. The RSA cryptographic system — which secures most HTTPS traffic — depends on extended Euclidean to compute private keys. Every time your browser establishes a TLS connection, a variant of this algorithm runs.

The extended Euclidean algorithm (Bézout's identity: ax + by = GCD(a,b)) is the computational backbone of modular inverses. Modular inverses are the backbone of modular arithmetic. Modular arithmetic is the backbone of RSA, Diffie-Hellman, elliptic curve cryptography, and the Chinese Remainder Theorem. The entire edifice of public-key cryptography rests on an algorithm Euclid described in 300 BC.

GCD, LCM, and the Euclidean Algorithm — The Math That Breaks RSA

The greatest common divisor (GCD) of two integers is the largest integer dividing both without remainder. The least common multiple (LCM) is the smallest positive integer divisible by both. The Euclidean algorithm computes GCD in O(log min(a,b)) steps by repeatedly replacing the larger number with the remainder of division: gcd(a,b) = gcd(b, a mod b). This is the oldest efficient algorithm still in daily use — and it's the foundation of RSA key generation.

Key property: for any two numbers, a × b = gcd(a,b) × lcm(a,b). This means you can compute LCM trivially once you have GCD. In practice, the Euclidean algorithm is the only practical way to compute GCD for large numbers — factoring is exponentially slower. The algorithm terminates because remainders shrink by at least half every two steps, guaranteeing logarithmic depth.

Use GCD whenever you need to reduce fractions, check coprimality (for RSA key generation), or compute modular inverses via the extended Euclidean algorithm. Use LCM when synchronizing periodic events or computing the least common denominator. In RSA, if p and q share a common factor (GCD > 1), the modulus n = p×q can be factored instantly — breaking the entire cryptosystem.

Euclidean Algorithm for GCD

Based on the identity: GCD(a, b) = GCD(b, a mod b). Repeat until b = 0 — then GCD = a.

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

def gcd_recursive(a: int, b: int) -> int:
    return a if b == 0 else gcd_recursive(b, a % b)

def lcm(a: int, b: int) -> int:
    return a * b // gcd(a, b)  # avoid overflow: a // gcd * b

print(gcd(252, 105))    # 21
print(gcd(48, 18))      # 6
print(lcm(12, 18))      # 36
print(lcm(4, 6))        # 12

# Python 3.9+ built-in
import math
print(math.gcd(252, 105))  # 21
print(math.lcm(12, 18))    # 36

GCD Implementations Across Languages

The Euclidean algorithm is nearly identical in every language. The key differences are handling of negative numbers and integer overflow. Below we show the iterative implementation in six widely used languages: C++, Java, C#, JavaScript, C, and Python (for completeness). All follow the same logic: while b != 0, set (a, b) = (b, a % b).

// C++ (modulo may return negative for negative inputs)
#include <cstdlib>
int gcd(int a, int b) {
    a = std::abs(a); b = std::abs(b);
    while (b) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// Java (similar to C++, use Math.abs)
public static int gcd(int a, int b) {
    a = Math.abs(a); b = Math.abs(b);
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}
// BigInteger version: a.gcd(b)

// C# (use Math.Abs, modulo is remainder, can be negative)
static int Gcd(int a, int b) {
    a = Math.Abs(a); b = Math.Abs(b);
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// JavaScript (Numbers are 64-bit floats, integer-safe up to 2^53)
function gcd(a, b) {
    a = Math.abs(a); b = Math.abs(b);
    while (b) {
        let t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// C (unsigned avoids sign issues, but handle negative externally)
unsigned int gcd(unsigned int a, unsigned int b) {
    while (b) {
        unsigned int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// Python (already shown above, included for completeness)
# def gcd(a,b): while b: a,b=b,a%b; return a

Visualizing the Euclidean Algorithm: Step by Step

Let's trace GCD(252, 105) step by step. The algorithm repeatedly replaces (a, b) with (b, a mod b) until b = 0. The final a is the GCD. We can see how quickly the numbers shrink — Lamé's theorem predicts at most 5×3 = 15 steps for 3-digit numbers, but we finish in just 4 steps.

Euclidean vs Binary GCD: Advantages and Disadvantages

Binary GCD (Stein's algorithm) is an alternative that replaces modulo with bit shifts and subtraction, which can be faster on processors with slow division. However, it is more complex and offers no advantage on modern hardware with fast modulo. Below is a comparison.

In most production systems, the standard Euclidean algorithm is preferred due to its simplicity and excellent performance. Binary GCD is reserved for environments where division is especially expensive.

Practice Problems on GCD and LCM

To solidify your understanding, work through these problems from competitive programming platforms. They cover GCD of arrays, coprime pairs, and Euler's totient, which directly build on the Euclidean algorithm.

1. [GCD of an Array](https://cses.fi/problemset/task/1080) (CSES) – Compute GCD of a list of numbers. A straightforward application.
2. [Coprime Pairs](https://www.codechef.com/problems/COPRIME) (CodeChef) – Count pairs in an array that are coprime. You'll need GCD(given pair) == 1.
3. [Euler's Totient Function](https://cses.fi/problemset/task/1081) (CSES) – Compute φ(n) for each n in a list. Formula: φ(n) = n * ∏(1 - 1/p). Needs prime factors and GCD concepts.
4. [LCM Sum](https://www.spoj.com/problems/LCMSUM/) (SPOJ) – Sum of LCMs from 1 to n. Requires efficient GCD and divisor enumeration.
5. [GCD Extreme](https://www.spoj.com/problems/GCDEX/) (SPOJ) – Sum of GCD of all pairs for numbers up to n. Uses Euler's totient and prefix sums.
6. [Modular Inverse](https://www.hackerrank.com/challenges/modular-inverse/problem) (HackerRank) – Compute x such that a*x ≡ 1 mod m. Direct extended GCD.
7. [RSA Key Generation](https://www.cryptool.org/en/cto/highlights/rsa-step-by-step) (CrypTool) – Practice key generation involving GCD and modular inverse.
8. [Binomial Coefficients and GCD](https://atcoder.jp/contests/abc156/tasks/abc156_d) (AtCoder) – Uses GCD for fraction simplification.

The Extended Euclidean Algorithm: Your Backdoor Into RSA

GCD alone is useful. The Extended Euclidean Algorithm is where you earn your paycheck. It doesn't just compute gcd(a, b). It finds integers x and y such that ax + by = gcd(a, b).

Why should you care? Because that x is the modular inverse of a modulo b when a and b are coprime. Modular inverses are the skeleton key for RSA key generation, the Chinese Remainder Theorem, and every asymmetric cryptosystem in production.

You run the standard Euclidean steps, but you also track the coefficients. When the recursion unwinds, you back-substitute to get x and y. The math is simple recursion. In practice, you'll hit stack limits on large numbers. Use the iterative version. Don't learn it in an interview; know it because your crypto library's bottleneck is here.

// io.thecodeforge — dsa tutorial

public class ExtendedEuclideanRsaKeygen {
    // Returns array [gcd, x, y] such that a*x + b*y = gcd
    public static int[] extendedGcd(int a, int b) {
        if (b == 0) return new int[]{a, 1, 0};
        int[] prev = extendedGcd(b, a % b);
        int gcd = prev[0];
        int x1 = prev[1];
        int y1 = prev[2];
        return new int[]{gcd, y1, x1 - (a / b) * y1};
    }

    public static void main(String[] args) {
        int a = 97, b = 61;
        int[] result = extendedGcd(a, b);
        System.out.println("GCD: " + result[0]);
        System.out.println("x: " + result[1]);
        System.out.println("y: " + result[2]);
        System.out.println("Verification: " + (a*result[1] + b*result[2]));
    }
}

LCM from GCD: Don't Multiply Then Divide

Everyone knows LCM(a, b) = (a * b) / gcd(a, b). That formula works. Until it doesn't.

In production, a and b are often large. 32-bit integers overflow when you multiply them. 64-bit too if you're working with crypto-sized numbers. The fix is trivial: divide before you multiply. Compute a / gcd(a, b) first, then multiply by b. The result stays in range as long as the LCM itself fits.

This isn't academic. I've seen a payment processing pipeline silently corrupt order totals because an intern used the naive formula. The fraction (a/gcd) gives you the reduced factor. Multiply last. Every library that matters does this: BigInteger, std::lcm in C++17, Python's math.lcm. Follow their lead.

For arrays, compute pairwise: lcm = gcdReduce(lcmSoFar, next). Don't compute product of entire array — that's asking for overflow.

// io.thecodeforge — dsa tutorial

public class LcmSafeOrderProcessor {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static int lcm(int a, int b) {
        // Divide first to avoid overflow
        return (a / gcd(a, b)) * b;
    }

    public static void main(String[] args) {
        int[] quantities = {12, 18, 24, 36};
        int result = 1;
        for (int qty : quantities) {
            result = lcm(result, qty);
        }
        System.out.println("LCM of production batch sizes: " + result);
    }
}