更高级的数论
Ruiqun2009
·
2024-12-10 10:40:12
·
算法·理论
二次剩余
注意到在二次筛法（在“分解”一文中提到）中要使用在 \bmod N 意义下是二次剩余的素数作为 factor base 中的素数，并进行试除法。
但是 N 不是素数，所以我们需要计算的不是 Legendre 符号，而是 Jacobi 符号。
Jacobi 符号：拥有二次互反律，完全积性，可以 O(\log^2 n) 计算。
\begin{aligned}
(\frac2n)&=(-1)^{\frac{n^2-1}8}\\
(\frac{a^b}{n})&=(\frac an)^b\\
(\frac ab)(\frac ba)&=(-1)^{\frac{(a-1)(b-1)}4}
\end{aligned}
这样就可以像计算 \gcd 一样计算这个符号了。
二次互反律：咕
被誉为数论定理之最，自 Gauß 于 1805 年获得第一个证明 [Ga86] 以来已经有了多余四百个证明。
### Fermat 数：$2^{2^n}+1(n\in\mathbb{Z^+})
目前已知 5 个素数，12 个已知完整分解结果，已知最大因子为 7\times2^{18233956}+1 。
注意到 3^{2^{2^n-1}}\equiv-1\pmod{2^{2^n}+1} 当且仅当 2^{2^n}+1 是素数。请根据二次互反律证明。
注意到 2^{2^n}+1 的因子必然有 k\times2^{n+2}+1 的形式。
Proof. 对于 n\leq3 显然成立。
将 p|2^{2^n}+1 写作 2^{2^n}\equiv-1\pmod p ，也意味着 \operatorname{ord}_p(2)=2^{n+1} 。由于 \forall a,\operatorname{ord}_p(a)|(p-1) ，有 2^{n+1}|p-1 ，即 p=k\times2^{n+1}+1 。
由此得到的 n>3 时 p=8k+1 可以推出 \sqrt{2}\bmod p 存在。所以 \operatorname{ord}_p(\sqrt2)=2^{n+2}|(p-1) ，即 p=k\times2^{n+2}+1 。
SNFS
选择多项式是个大话题。
这里默认 deg(alg poly) 最大为 8 。
a\times b^n+c 的因数很简单，按照这个形式构造就行了。
n: fac(a*b^n+c)
cdeg(alg poly): a*b^(n mod deg(alg poly))
c0: c
Y0: b^⌊n/deg(alg poly)⌋
Y1: -1y\times a^n+z\times b^n 的因数可以根据 y\times(\frac ab)^n+z 来构造（转化为 y\times m^n+z ，其中 m=\frac ab ）。
n: fac(y*a^n+z*b^n)
cdeg(alg poly): y*a^(n mod deg(alg poly))
c0: z*b^(n mod deg(alg poly))
Y0: a^⌊n/deg(alg poly)⌋
Y1: -b^⌊n/deg(alg poly)⌋a^n-1 的因数有几类情况（依次判断 ）：
* 若 $n$ 是 $15$ 的倍数，则可以构造四次多项式：
```
n: fac(a^(2n/3)+a^(n/3)+1)
c4: 1
c3: -1
c2: -4
c1: 4
c0: 1
Y0: a^(2n/15)+1
Y1: -a^(n/15)
```
* 否则，若 $n$ 是 $21$ 的倍数，则可以构造六次多项式：
```
n: fac(a^(2n/3)+a^(n/3)+1)
c6: 1
c5: -1
c4: -6
c3: 6
c2: 8
c1: -8
c0: 1
Y0: a^(2n/21)+1
Y1: -a^(n/21)
```
* 否则，若 $n$ 是 $9$ 的倍数，则可以构造六次多项式：
```
n: fac(a^(2n/3)+a^(n/3)+1)
c6: 1
c3: 1
c0: 1
Y0: a^(2n/9)
Y1: -1
```
* 否则，可以构造四次/六次多项式（分解的速度取决于多项式的好坏）。
x^y+y^x 的因数待填坑。
a^n+1 的因数和 a^n-1 的情况相近，只需将所有奇次项系数改为其相反数即可。
V(n,a,b) 的因数使用 g(x)=F_{\frac nk}x-F_{\frac nk+1} ，其中 k=5 或 6 （即令其有一个根 \approx\frac{\sqrt5+1}2 ）。
然后考虑用 F_{\frac nk}^m\times F_{\frac nk+1}^{k-m}(0<=m<=k) 的线性组合得到 V(n,a,b) 。这步使用 LLL 算法（参见 pari/gp 的 lindep 函数）。
快速计算 \text{e} 和 \pi
\text{e} 注意到
\text{e}=1+\sum_{i=1}^{\infty}\frac1{i!}
所以可以构造 p(a,b) 和 q(a,b) ，满足
\binom {p(a,b)}{q(a,b)}=\begin{cases}\binom {1}{b},&\text{if }b=a+1\text{,}\\\binom {p(a,m)q(m,b)+p(m,b)}{q(a,m)q(m,b)},&\text{otherwise, where }m=\lfloor (a+b)/2\rfloor.\end{cases}
然后计算 p(1,n)/q(1,n) 就是 \sum_{i=1}^\infty\frac1{i!} 。
\pi 使用 Chudnovsky's Formula。此法借助了 j(\frac{-1+\sqrt{-163}}2)=640320^3+744 的特点（可以使用 CM 验证：163 的 class number 为 1 ）。该方法的严密证明可以在 [Mi21] 中找到。
仍然使用 Binary Splitting。
\left(\begin{matrix}P(a,b)\\Q(a,b)\\R(a,b)\end{matrix}\right)=\begin{cases}\left(\begin{matrix}-(6a-1)(2a-1)(6a-5)\\10939058860032000a^3\\P(a,b)\times(545140134a+13591409)\end{matrix}\right),&\text{if }b=a+1,\\\left(\begin{matrix}P(a,m)P(m,b)\\Q(a,m)Q(m,b)\\Q(m,b)R(a,m)+P(a,m)R(m,b)\end{matrix}\right),&\text{otherwise, where }m=\lfloor(a+b)/2\rfloor.\end{cases}
最终 \pi =\lim_{n\to\infty}{\frac{426880{\sqrt {10005}}\times Q(1,n)}{13591409Q(1,n)+R(1,n)}} 。
References
[Ga86] Gauss, Carl Friedrich. Disquisitiones Arithmeticae . Springer, 1986.
[Mi21] Milla, Lorenz. “A Detailed Proof of the Chudnovsky Formula with Means of Basic Complex Analysis.” Number Theory , 16 Mar. 2021, doi:10.48550/arXiv.1809.00533.