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.

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.

Frequently Asked Questions