1. 小步大步算法的边界中群阶 p 已知与未知时的处理差异，以及素数阶子群的安全意义？
问题
BSGS（Baby-Step Giant-Step）算法在求解离散对数时，当群阶 p 已知与未知时处理有什么差异？素数阶子群在安全上有什么意义？
考察点
- BSGS 算法对群阶的依赖
- 素数阶子群的安全性质
- 群阶已知/未知时的处理策略
答案
BSGS 求解离散对数 a^x ≡ b (mod p) 时，其时间与空间复杂度都是 O(√p)，其中 p 是群的阶。若群阶 p 已知，可直接令 m = ⌈√p⌉，将 x 写成 x = im + j（0 ≤ j < m），先计算 baby steps a^j 存入哈希表，再计算 giant steps b·(a^{-m})^i 逐项在表中查找。若群阶未知，则无法立即确定 m，需要先估计或确定群阶，或改用不需要先验群阶的 Pollard Rho 方法。素数阶子群的安全意义在于：当群阶 q 为素数时，该群没有非平凡子群，攻击者无法利用子群结构（如小群攻击、Pohlig-Hellman 分解群阶）来降低离散对数难度，因此素数阶子群是密码学中的"安全群"。
解析
BSGS 的核心是把离散对数问题分解成"小步"与"大步"两个部分，利用哈希表存 baby steps 换取 O(1) 查找，从而把 O(p) 的暴力降为 O(√p)。群阶已知与否直接决定 m 的选取，实际密码系统中通常固定使用素数阶子群（如安全素数 p=2q+1 的 q 阶子群）。
示例代码
// BSGS: 求 x 使 a^x ≡ b (mod p)，p 为素数（群阶）
int bsgs(int a, int b, int p) {
a %= p; b %= p;
if (b == 1) return 0;
int m = (int) Math.ceil(Math.sqrt(p));
Map<Integer, Integer> table = new HashMap<>();
long cur = 1;
for (int j = 0; j < m; j++) { // baby steps
table.putIfAbsent((int) cur, j);
cur = cur * a % p;
}
long factor = modInv(a, p); // a^{-1}
long step = modPow(factor, m, p); // a^{-m}
long curGiant = b;
for (int i = 0; i < m; i++) { // giant steps
if (table.containsKey((int) curGiant)) return i * m + table.get((int) curGiant);
curGiant = curGiant * step % p;
}
return -1; // 无解
}