每日算法 — 使用java实现欧几里得算法：辗转相除法与扩展欧几里得求模逆元

引言

欧几里得算法（Euclidean Algorithm）是数论中最古老、最优雅的算法之一，距今已有两千多年的历史。它用于高效计算两个整数的最大公约数（Greatest Common Divisor, GCD），其核心思想”辗转相除”简单却极其深刻。扩展欧几里得算法（Extended Euclidean Algorithm）在此基础上更进一步，不仅能求出 GCD，还能找到满足贝祖等式 ax + by = gcd(a, b) 的整数解 x 和 y。这一能力使得扩展欧几里得算法在模逆元计算、RSA 密码学、线性丢番图方程求解等领域有着不可替代的作用。本文将用 Java 完整实现这两种算法，并深入探讨其数学原理与实际应用。

最大公约数的数学基础

对于两个正整数 a 和 b，它们的最大公约数 gcd(a, b) 是能同时整除 a 和 b 的最大正整数。

关键定理： gcd(a, b) = gcd(b, a mod b)

这意味着：a 和 b 的最大公约数，等于 b 和 a 除以 b 的余数的最大公约数。由于余数一定小于 b，问题的规模在每一步都严格减小，因此算法必然在有限步内终止。

辗转相除法（基础欧几里得算法）

递归实现

/**
 * 欧几里得算法（辗转相除法）递归实现
 * 计算两个非负整数的最大公约数
 * 时间复杂度：O(log min(a, b))
 * 空间复杂度：O(log min(a, b)) — 递归栈深度
 *
 * @param a 第一个非负整数
 * @param b 第二个非负整数
 * @return a 和 b 的最大公约数
 */
public static int gcdRecursive(int a, int b) {
    // 基准情况：如果 b 为 0，则 gcd(a, 0) = a
    if (b == 0) {
        return a;
    }
    // 递归调用：gcd(a, b) = gcd(b, a % b)
    return gcdRecursive(b, a % b);
}

迭代实现（推荐）

/**
 * 欧几里得算法迭代实现
 * 避免了递归栈溢出的风险，更适合大数计算
 * 时间复杂度：O(log min(a, b))
 * 空间复杂度：O(1)
 */
public static int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;  // 计算余数
        a = temp;   // 将 b 的值赋给 a
    }
    return a;
}

支持 long 类型的版本

/**
 * 支持 long 类型的 GCD 计算
 * 用于处理大整数场景
 */
public static long gcdLong(long a, long b) {
    while (b != 0) {
        long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

扩展欧几里得算法

扩展欧几里得算法不仅求出 gcd(a, b)，还找到满足贝祖等式 ax + by = gcd(a, b) 的整数系数 x 和 y。

数学推导

假设我们已经知道 gcd(b, a mod b) 的解 (x’, y’)，即：

bx' + (a mod b)y' = gcd(a, b)

由于 a mod b = a – ⌊a/b⌋ × b，代入得：

bx' + (a - ⌊a/b⌋ × b)y' = gcd(a, b)
ay' + b(x' - ⌊a/b⌋ × y') = gcd(a, b)

因此：

x = y'
y = x' - ⌊a/b⌋ × y'

Java 实现

/**
 * 扩展欧几里得算法
 * 返回三元组 (g, x, y)，满足 ax + by = g = gcd(a, b)
 * 时间复杂度：O(log min(a, b))
 */
public static long[] extendedGcd(long a, long b) {
    if (b == 0) {
        // 基准情况：gcd(a, 0) = a，此时 x=1, y=0
        return new long[]{a, 1, 0};
    }

    // 递归求解 gcd(b, a % b)
    long[] next = extendedGcd(b, a % b);
    long g = next[0];
    long x1 = next[1];  // x' —— b 的系数
    long y1 = next[2];  // y' —— (a % b) 的系数

    // 根据推导公式回推当前层的 x 和 y
    long x = y1;
    long y = x1 - (a / b) * y1;

    return new long[]{g, x, y};
}

迭代版本实现

/**
 * 扩展欧几里得算法的迭代实现
 * 使用矩阵迭代法，空间复杂度 O(1)
 */
public static long[] extendedGcdIterative(long a, long b) {
    long oldR = a, r = b;
    long oldS = 1, s = 0;
    long oldT = 0, t = 1;

    while (r != 0) {
        long quotient = oldR / r;

        // (oldR, r) = (r, oldR - quotient * r)
        long tempR = r;
        r = oldR - quotient * r;
        oldR = tempR;

        // (oldS, s) = (s, oldS - quotient * s)
        long tempS = s;
        s = oldS - quotient * s;
        oldS = tempS;

        // (oldT, t) = (t, oldT - quotient * t)
        long tempT = t;
        t = oldT - quotient * t;
        oldT = tempT;
    }

    // oldR = gcd(a, b)，oldS = x，oldT = y
    return new long[]{oldR, oldS, oldT};
}

模逆元计算

模逆元是密码学中的核心概念。若 ax ≡ 1 (mod m)，则称 x 为 a 模 m 的逆元，记作 a⁻¹ (mod m)。

存在条件： a 模 m 的逆元存在，当且仅当 gcd(a, m) = 1。

/**
 * 计算 a 模 m 的模逆元
 * 前提条件：gcd(a, m) = 1
 * 使用扩展欧几里得算法：ax + my = 1，则 x mod m 即为逆元
 *
 * @param a 待求逆元的数
 * @param m 模数
 * @return a 模 m 的逆元，若不存在则返回 -1
 */
public static long modInverse(long a, long m) {
    long[] result = extendedGcdIterative(a, m);
    long g = result[0];
    long x = result[1];

    if (g != 1) {
        return -1;  // 逆元不存在
    }

    // 确保结果在 [0, m-1] 范围内
    return (x % m + m) % m;
}

线性丢番图方程求解

形如 ax + by = c 的方程，有整数解的条件是 gcd(a, b) 能整除 c。

/**
 * 求解线性丢番图方程 ax + by = c
 * 返回一个特解 (x0, y0)，以及通解的步长
 * 通解形式：x = x0 + (b/g)*t, y = y0 - (a/g)*t
 */
public static class DiophantineSolution {
    public boolean hasSolution;
    public long x0, y0;      // 特解
    public long stepX, stepY; // 通解步长

    public DiophantineSolution(boolean has, long x0, long y0, long sx, long sy) {
        this.hasSolution = has;
        this.x0 = x0; this.y0 = y0;
        this.stepX = sx; this.stepY = sy;
    }
}

public static DiophantineSolution solveDiophantine(long a, long b, long c) {
    long[] egcd = extendedGcdIterative(Math.abs(a), Math.abs(b));
    long g = egcd[0];

    if (c % g != 0) {
        return new DiophantineSolution(false, 0, 0, 0, 0);
    }

    long scale = c / g;
    long x0 = egcd[1] * scale;
    long y0 = egcd[2] * scale;

    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;

    return new DiophantineSolution(true, x0, y0, b / g, -a / g);
}

完整工具类与测试

public class EuclideanAlgorithm {

    // 基础 GCD
    public static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    // 多个数的 GCD
    public static long gcdMultiple(long... numbers) {
        long result = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            result = gcd(result, numbers[i]);
            if (result == 1) break;
        }
        return result;
    }

    // 最小公倍数 LCM
    public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;  // 先除后乘防止溢出
    }

    // 扩展欧几里得
    public static long[] extendedGcd(long a, long b) {
        if (b == 0) return new long[]{a, 1, 0};
        long[] next = extendedGcd(b, a % b);
        long x = next[2];
        long y = next[1] - (a / b) * next[2];
        return new long[]{next[0], x, y};
    }

    // 模逆元
    public static long modInverse(long a, long mod) {
        long[] egcd = extendedGcd(a, mod);
        if (egcd[0] != 1) return -1;
        return (egcd[1] % mod + mod) % mod;
    }

    public static void main(String[] args) {
        // 测试 GCD
        System.out.println("gcd(48, 18) = " + gcd(48, 18));  // 6
        System.out.println("gcd(1071, 462) = " + gcd(1071, 462));  // 21

        // 测试扩展欧几里得
        long[] egcd = extendedGcd(30, 12);
        System.out.println("\n30x + 12y = " + egcd[0]);
        System.out.println("x = " + egcd[1] + ", y = " + egcd[2]);
        System.out.println("验证: " + (30 * egcd[1] + 12 * egcd[2]));

        // 测试模逆元
        long inv = modInverse(3, 11);
        System.out.println("\n3 模 11 的逆元 = " + inv);  // 4
        System.out.println("验证: (3 * " + inv + ") % 11 = " + (3 * inv % 11));

        // 测试 LCM
        System.out.println("\nlcm(12, 18) = " + lcm(12, 18));  // 36
    }
}

算法复杂度分析

总结

欧几里得算法以其两千年的悠久历史和极致的简洁性，堪称算法设计中最优雅的典范之一。辗转相除的核心思想——将大问题转化为规模更小但结构相同的子问题——正是递归与分治思想的原始雏形。扩展欧几里得算法在此基础上更进一步，通过反向递推贝祖系数，赋予了这一古老算法在现代密码学中的新生。掌握欧几里得算法及其扩展，不仅是数论学习的基础，更是理解 RSA、Diffie-Hellman 等现代加密体系的关键一步。