分享一些的数论杂谈吧，可能没什么关联性。

Jacobi符号

对任意整数$a$,正奇数$n$有Jacobi符号$(a|n)$

$(a|1)=1$

$n$为素数时$(a|n)$就是Legendre符号

$a$为定值时$(a|n)$关于$n$的完全积性函数

算法：

$(a|1)=1$

$(a|n)=(a \bmod n|n)$

$(2a|n)=(2|n)(a|n)$

$(2|n)=(-1)^{\frac{n^2-1}{8}}$

若$\gcd(a,n)\neq 1$ 则 $(a|n)=0$

此时$\gcd(a,n)=1,a< n$ 为正奇数有

$(a|n)(n|a)=(-1)^{\frac{(a-1)(n-1)}{4}}$

Lucas序列

$U_{n}(P,Q),V_{n}(P,Q)$都满足$x_{n+2}=Px_{n+1}-Qx_{n}$

$U_{0}=0,U_{1}=1.V_{0}=2,V_{1}=P$

矩阵快速幂求就好了

Lucas拟素数检验

对奇数$N>1$,选定$(P,Q).D=P^2-4Q$

若$\gcd(DQ,N)=1,U_{N-(D|N)}\pmod N \equiv 0$则$N$是拟素数

否则$N$是合数

强Lucas拟素数检验

令$N-(D|N)=2^rs$,$s$为奇数

若$U_{s}\pmod N \equiv 0$或$\exists 0\leq i < r$使$V_{2^is}\pmod N \equiv 0$

则$N$是拟素数，否则$N$是合数

Baillie-PSW素性检验

检查$N$是否是完全平方数，若是则$N$是合数

执行以$2$为底的Miller-Rabin检验；若未能通过检验，则$N$是合数

找到$5,-7,9,-11,\cdots$第一个满足$(D|N)=-1$的$D$,令$P=1,Q=\frac{1-D}{4}$

执行$(P,Q)$的强Lucas拟素数检验；若未能通过检验，则$N$是合数

目前无反例。

$10^{18}$范围内跑起来比单纯Miller-Rabin要慢一点

我的代码

参考文献1