26、数论中的离散对数、二次剩余及相关符号计算

数论中的离散对数、二次剩余及相关符号计算

离散对数相关算法

在离散对数的研究领域，有诸多重要的算法和结论。首先是关于区分“Diffie - Hellman 三元组”和“随机三元组”的问题。当底层群的阶不被任何小素数整除时，区分这两种三元组是困难的，这也是我们选择大素数阶群进行研究的另一个原因。

对于寻找 $Z_p^$ 生成元的概率算法，在黎曼假设的推广下可以使其确定性化。在这种假设下，对于每个素数 $q | (p - 1)$，使得 $[a]_p \in Z_p^\setminus (Z_p^*)^q$ 的最小正整数 $a$ 至多为 $2 \log p$。

关于 $Z_p^*$ 最小正原根的大小问题，在黎曼假设的推广下，Wang 证明了模 $p$ 的最小原根为 $O(r^6 \text{len}(p)^2)$，其中 $r$ 是 $p - 1$ 的不同素因数的个数。Shoup 通过改进 Iwaniec 的结果并应用到 Wang 的证明中，将这个界限提高到了 $O(r^4 \text{len}(r)^4 \text{len}(p)^2)$。而无条件的最小原根模 $p$ 的最佳界限是 $p^{1/4 + o(1)}$。不过，即使存在小的原根，在不知道 $p - 1$ 的素因数分解的情况下，也没有已知的有效方法来识别模 $p$ 的原根。

这里介绍的离散对数算法具有“通用性”，它们适用于任何有限循环群，并且在这类“通用”算法中，这些离散对数算法是最优的。但对于 $Z_p^*$ 中的离散对数，也存在更快的“非通用”算法（虽然仍不是多项式时间的）。

以下是一些具体的离散对数算法：
-“婴儿步/巨人步”