高置信度质数测试与F₂⁶⁰⁷离散对数计算

### 高置信度素性测试与特征 2 有限域离散对数计算 #### 1. 高置信度素性测试 在素性测试中，当\(\omega(n) = 2\)时，我们区分以下几种情况： - **情况一**：假设对于某个整除\(n\)的素数\(p\)，有\(2^{\nu(n)+2}\mid p - 1\)，那么\(2^{\nu(n)-1}\gcd(s, p - 1) \leq (p - 1)/8\)，从而\(\varphi(n)/(2^{\#S_{-1}(n)}) \geq 1/2 \cdot (2 \cdot 8) = 8\)。 - **情况二**：设对于某个整除\(n\)的素数\(p\)，有\(2^{\nu(n)+\delta}\mid p - 1\)，其中\(\delta\)等于\(0\)或\(1\)。将两个素数写成\(p_1 = 2^{\nu(n)+\delta}t_1 + 1\)和\(p_2 = 2^{\nu(n)}t_2 + 1\)的形式。 - 当\(t_1 \neq t_2\)时，\(t_1\mid s\)和\(t_2\mid s\)不可能同时成立。这意味着对于至少一个\(p_i\)，\(\gcd(s, p_i - 1) \leq t_i/3\)。 - 若\(\delta = 0\)，则\(\varphi(n)/(2^{\#S_{-1}(n)}) \geq 1/2 \cdot (2 \cdot 6) = 6\)；若\(\delta = 1\)，会引入一个额外的因子\(2\)，使得\(\varphi(n)/(2^{\#S_{-1}(n)}) \geq 12\)。 - **特殊情况**：当\(p_1 = 2^kt + 1\)且\(p_2 = 2^{k + 1}t + 1\)时，\(t\mid s\)，此时由于\(2^{\nu(n)+1}\mid p_2 - 1\)，有\(\varphi(n)/(2^{\#S_j(n)}) \geq 1/2 \cdot (2 \cdot 4)\)。 在证明主要结果时，假设\(n\)是三个不同素因子的乘积，定理 3 和引理 2（或引理 3）可得出相应结果。对于基于 Atkin 的根查找方法，引理 3 表明\(n\)是\(spsp(2d^2)\)。由于对于\(n \equiv 5 \mod 8\)有\(\left(\frac{2d^2}{n}\right) = -1\)，我们可以应用引理 6。假设在平方根查找算法中随机选择\(d\)，对于这个基的随机选择，\(n\)是\(spsp(2d^2)\)的条件与基于二次 Frobenius（QF）的测试无关。 若\(n\)不是引理 6 中描述的特殊双因子整数，除了定理 3 中检查 QF 条件的测试所得到的失败概率外，每个随机\(d\)会引入一个\(1/8\)的因子。若\(n\)通过基于 Shanks 的方法，它首先是对于满足\(\left(\frac{u}{n}\right) = -1\)的\(u\)的\(spsp(u)\)。对于随机选择的\(u\)，这同样会在失败概率中引入一个\(1/8\)的因子。 对于两种类型的根查找算法，如果\(n\)具有特殊的双因子形式，命题 4 引入的失败率比上述情况小得多（基于\(\gcd(n + 1, p \pm 1)\)的 QF 伪素数的相应数量，当\(p - 1\)的奇数部分整除\(n - 1\)时会变得小得多）。总体而言，对于\(\omega = 2\)，最大的失败率适用于一般类型的双因子数。 失败率方面，第一轮的失败率\(F_1 = 1/2^{20} + 1/(2B^2)\)，对于\(k - 1\)次额外迭代，失败率为\(F_1 \cdot (1/2^{17} + 4/B^2)^{k - 1}\)。对于较大的\(k\)，\(B\)的比例可以忽略不计，因此对于总共\(k\)轮，失败率近似为\(1/(2^{20} \cdot 2^{17(k - 1)}) = 1/2^{17k + 3}\)。 下面通过表格总结不同情况下的相关参数和结果： |情况|条件|结果| | ---- | ---- | ---- | |情况一|\(2^{\nu(n)+2}\mid p - 1\)（\(p\mid n\)）|\(\varphi(n)/(2^{\#S_{-1}(n)}) \geq 8\)| |情况二 - \(\delta = 0\)|\(2^{\nu(n)}\mid p - 1\)（\(p\mid n\)），\(t_1 \neq t_2\)|\(\varphi(n)/(2^{\#S_{-1}(n)}) \geq 6\)| |情况二 - \(\delta = 1\)|\(2^{\nu(n)+1}\mid p - 1\)（\(p\mid n\)），\(t_1 \neq t_2\)|\(\varphi(n