一类新的素性测试法
wanganze
·
·
算法·理论
声明
本文内容主要由我的同学 hjh 发现，其中部分结论未严格证明，如能给出则不胜感激，文中可能会有错误之处，如有发现请私信联系我。发表时已经过他的授权，未经他许可不得转载。
本文主要介绍一些结论。
引入
我们注意到一个数列 https://oeis.org/A001608 它的下面一些链接，例如这篇上古论文和这个讨论提到了它可以用于素性测试，但是 https://oeis.org/A013998 给出了伪素数。
好像有论文给出这个数列的伪素数是 O(\log n) 的，但是根据 oeis，伪素数非常多。
三阶递推
我们注意到原数列可以推广：
\Z
其特征方程为 r^3=1+Ar，判别式 \Delta=27-4A^3。
下面证明对于所有素数 p，有 p\mid a_p。
发现较小的两个素数都成立，不妨设 p=6q+2r-1, q\in \N_+, r\in \{0,1\}。
我们可以直接计算出 a_p。
a_p=\sum\limits_{0\le i<j\le n}C_p^{3i+r+1}C_{2q-2i-1}^{2q-2j}\cdot A^{3i+r+1}\cdot 2^{-2q-2i+2}\cdot 3^{-3-3q-r+3j}\cdot\Delta^{q-j}\in \Z
又 3i+r+1\ne0, p，故对于所有素数 p，有 p\mid C_p^{3i+r+1}，故 p\mid a_p。
也就是说我们可以通过选取合适的基 A 来实现一个素性测试。这样的好处是可以让伪素数大大减少。虽然还没有证明不存在绝对伪素数，但是实验测试没有发现这种数。
一组判断奇素数的合适的基是 1, 6。
时间复杂度小范围 O(\log n)，考虑高精度的大范围为 O(k \log^2n \log \log n \log \log \log n) ，看上去和 miller rabin 一样。但是矩阵快速幂常数好大啊。
类似地，可以继续推广，对于 a_1=0, a_2=2A, a_3=3B, a_{n+3}=Aa_{n+1}+Ba_n, A, B\in
\Z 也有 p\mid a_p。
二阶递推
对于数列 a_{n+2}=Aa_{n+1}+Ba_n, A, B\in
\Z，则对奇素数 p，a_p\equiv\dfrac{1}{2}\left(a_0A+(2a_1-a_0A)\left(\dfrac{A^2+4B}{p}\right)\right) \pmod p，其中 \left(\dfrac{q}{p}\right) 为勒让德符号。
我们可以赋值初项来消去勒让德符号。
考虑以下数列：
a_0=2, a_1=1,a_{n+2}=a_{n+1}+Aa_n, A\in \Z
则对于所有素数 p，a_p\equiv1\pmod p。
这时也可以通过取合适的基实现素性测试。
推广：a_0=2, a_1=A,a_{n+2}=Aa_{n+1}+Ba_n, A, B\in \Z，对于所有素数 p，a_p\equiv A\pmod p。
总结
复杂度没有优势，但是矩阵快速幂常数更大，所以暂时没有实际用途。