每日算法 — 使用java实现大步小步算法：离散对数问题的分步求解策略

引言

大步小步算法（Baby-step Giant-step，简称BSGS）是数论中解决离散对数问题（Discrete Logarithm Problem）的经典算法。给定同余方程 a^x ≡ b (mod p)，BSGS能在O(√p)时间复杂度内求出x，远优于O(p)的暴力枚举。该算法是密码学（特别是椭圆曲线密码）的基础工具之一，其”分而治之”的思想也广泛应用于其他算法设计场景。本文将用Java完整实现BSGS，并讲解其数学原理与应用扩展。

问题定义与数学背景

离散对数问题

在模p乘法群Z_p*中（p为素数），给定生成元a和目标值b，求满足以下同余式的最小非负整数x：

a^x ≡ b (mod p)

x称为b以a为底的离散对数，记作 x = log_a(b) mod p。

核心思想：分而治之

设 m = ⌈√p⌉，将x表示为 x = i·m + j，其中 0 ≤ i, j < m。

则：a^(i·m+j) ≡ b (mod p) ⇒ a^j ≡ b·(a^(-m))^i (mod p)

算法分两步：
1. Baby-step：预计算所有 a^j mod p，存入哈希表
2. Giant-step：枚举i，计算 b·(a^(-m))^i mod p，在哈希表中查找匹配

Java实现

import java.util.HashMap;
import java.util.Map;
import java.math.BigInteger;

/**
 * 大步小步算法（Baby-step Giant-step）
 * 求解离散对数问题: a^x ≡ b (mod p)
 */
public class BabyStepGiantStep {

    /**
     * 扩展欧几里得算法：求a在模mod下的乘法逆元
     * 即求满足 a·inv ≡ 1 (mod mod) 的inv
     *
     * @param a   待求逆元的数
     * @param mod 模数
     * @return 乘法逆元，若不存在返回-1
     */
    public static long modInverse(long a, long mod) {
        long[] egcd = extendedGcd(a, mod);
        long g = egcd[0], x = egcd[1];
        if (g != 1) {
            return -1; // 逆元不存在
        }
        return ((x % mod) + mod) % mod;
    }

    /**
     * 扩展欧几里得算法
     * 返回 [g, x, y] 满足 ax + by = g = gcd(a,b)
     */
    private static long[] extendedGcd(long a, long b) {
        if (b == 0) {
            return new long[]{a, 1, 0};
        }
        long[] next = extendedGcd(b, a % b);
        long g = next[0], x1 = next[1], y1 = next[2];
        long x = y1;
        long y = x1 - (a / b) * y1;
        return new long[]{g, x, y};
    }

    /**
     * 快速幂：计算 (base^exp) % mod
     */
    public static long modPow(long base, long exp, long mod) {
        long result = 1;
        long b = ((base % mod) + mod) % mod;
        long e = exp;
        while (e > 0) {
            if ((e & 1) == 1) {
                result = (result * b) % mod;
            }
            b = (b * b) % mod;
            e >>= 1;
        }
        return result;
    }

    /**
     * BSGS核心算法：求解 a^x ≡ b (mod p)
     * 前提条件：p为素数，a为原根或a与p互质
     *
     * @param a 底数
     * @param b 目标值
     * @param p 素数模数
     * @return 最小非负整数解x，无解返回-1
     */
    public static long bsgs(long a, long b, long p) {
        a = ((a % p) + p) % p;
        b = ((b % p) + p) % p;

        if (b == 1) {
            return 0; // a^0 = 1
        }
        if (a == 0) {
            return b == 0 ? 1 : -1;
        }

        // 计算 m = ceil(sqrt(p))
        long m = (long) Math.ceil(Math.sqrt(p));

        // ===== Baby-step：预计算 a^j mod p =====
        Map<Long, Long> babySteps = new HashMap<>();
        long current = 1; // a^0 = 1
        for (long j = 0; j < m; j++) {
            // 存储最小的j值（如果存在多个）
            babySteps.putIfAbsent(current, j);
            current = (current * a) % p;
        }

        // ===== Giant-step：枚举 i =====
        // 计算 a^(-m) mod p = (a^m)^(-1) mod p
        long am = modPow(a, m, p);
        long amInv = modInverse(am, p);
        if (amInv == -1) {
            return -1; // 逆元不存在
        }

        current = b; // 初始值：b * (a^(-m))^0 = b
        for (long i = 0; i < m; i++) {
            if (babySteps.containsKey(current)) {
                long j = babySteps.get(current);
                long x = i * m + j;
                // 验证解
                if (modPow(a, x, p) == b) {
                    return x;
                }
            }
            current = (current * amInv) % p;
        }

        return -1; // 无解
    }

    /**
     * 使用BigInteger的版本，支持更大的数
     */
    public static BigInteger bsgsBig(BigInteger a, BigInteger b, BigInteger p) {
        if (b.equals(BigInteger.ONE)) {
            return BigInteger.ZERO;
        }

        BigInteger m = sqrt(p).add(BigInteger.ONE);

        // Baby-step
        Map<BigInteger, BigInteger> table = new HashMap<>();
        BigInteger aj = BigInteger.ONE;
        for (BigInteger j = BigInteger.ZERO;
             j.compareTo(m) < 0;
             j = j.add(BigInteger.ONE)) {
            table.putIfAbsent(aj, j);
            aj = aj.multiply(a).mod(p);
        }

        // Giant-step
        BigInteger am = a.modPow(m, p);
        BigInteger amInv = am.modInverse(p);
        BigInteger cur = b;
        for (BigInteger i = BigInteger.ZERO;
             i.compareTo(m) < 0;
             i = i.add(BigInteger.ONE)) {
            if (table.containsKey(cur)) {
                BigInteger j = table.get(cur);
                BigInteger x = i.multiply(m).add(j);
                if (a.modPow(x, p).equals(b)) {
                    return x;
                }
            }
            cur = cur.multiply(amInv).mod(p);
        }

        return BigInteger.valueOf(-1);
    }

    private static BigInteger sqrt(BigInteger n) {
        BigInteger x = n;
        BigInteger y = BigInteger.ONE;
        while (x.subtract(y).compareTo(BigInteger.ONE) > 0) {
            x = x.add(y).shiftRight(1);
            y = n.divide(x);
        }
        return x;
    }

    // ==================== 测试与演示 ====================

    public static void main(String[] args) {
        System.out.println("=== 大步小步算法（BSGS）演示 ===\n");

        // 示例1: 3^x ≡ 7 (mod 17)，已知解为x=11
        System.out.println("【示例1】求解 3^x ≡ 7 (mod 17)");
        long a1 = 3, b1 = 7, p1 = 17;
        long x1 = bsgs(a1, b1, p1);
        System.out.printf("解: x = %d%n", x1);
        System.out.printf("验证: 3^%d mod 17 = %d%n%n", x1, modPow(a1, x1, p1));

        // 示例2: 5^x ≡ 13 (mod 23)
        System.out.println("【示例2】求解 5^x ≡ 13 (mod 23)");
        long a2 = 5, b2 = 13, p2 = 23;
        long x2 = bsgs(a2, b2, p2);
        System.out.printf("解: x = %d%n", x2);
        if (x2 >= 0) {
            System.out.printf("验证: 5^%d mod 23 = %d%n%n", x2, modPow(a2, x2, p2));
        }

        // 示例3: 大素数测试
        System.out.println("【示例3】求解 2^x ≡ 12345 (mod 1000003)");
        long a3 = 2, b3 = 12345, p3 = 1000003;
        long start = System.currentTimeMillis();
        long x3 = bsgs(a3, b3, p3);
        long elapsed = System.currentTimeMillis() - start;
        System.out.printf("解: x = %d (耗时 %d ms)%n", x3, elapsed);
        if (x3 >= 0) {
            System.out.printf("验证: 2^%d mod 1000003 = %d%n%n", x3, modPow(a3, x3, p3));
        }

        // 示例4: BigInteger版本
        System.out.println("【示例4】BigInteger大数测试");
        BigInteger ba = new BigInteger("2");
        BigInteger bb = new BigInteger("54321");
        BigInteger bp = new BigInteger("10000019");
        BigInteger bx = bsgsBig(ba, bb, bp);
        System.out.printf("解: x = %s%n", bx.toString());
        System.out.printf("验证: 2^%s mod 10000019 = %s%n",
                          bx, ba.modPow(bx, bp));
    }
}

复杂度分析

扩展与变种

扩展BSGS（处理a与p不互质的情况）

当gcd(a, p) ≠ 1时，标准BSGS失效。扩展版本通过提取公因子逐步降阶处理。

Pollard’s Rho算法

另一种离散对数算法，期望时间复杂度O(√p)，但空间复杂度仅为O(1)，适合内存受限场景。

应用场景

1. 密码学分析：评估离散对数密码体制的安全性
2. Diffie-Hellman密钥交换：安全性基于离散对数问题的困难性
3. 椭圆曲线密码：椭圆曲线上的离散对数问题（ECDLP）
4. 竞赛编程：数论题目的标准解法（如求解a^x ≡ b mod p）

总结

大步小步算法将指数搜索空间从O(p)降低到O(√p)，是” meet-in-the-middle”（中间相遇）策略的经典应用。其核心思想——将问题分解为预计算和查询两个阶段——不仅适用于离散对数，也启发了大量分治算法的设计。掌握BSGS有助于深入理解密码学安全假设与算法效率之间的博弈关系。