《初等数论及其运用》6.1 章节
Wilson 定理
对于 \(p\)，
\[ (p - 1)! \equiv \left\{ \begin{array}{ll} -1 & p 是素数 \\ 2 & p = 4\\ 0 & p \neq 4 且是合数\\ \end{array} \right. \]证明：
对于素数，利用缩系的性质证明。
对于合数，考虑分解 \(p=ab\)，然后考虑 \((p-1)!\) 里面是否包含 \(a,b\) 即可。很容易证明。
Fermat 小定理
对于 \((a,p) = 1\)，有 \(a^{p-1} \equiv 1(\bmod p)\)。
判断素数
miller-rabin 算法
寻找因子
pollard p-1 算法
当 \(n\) 存在素数 \(p\)，并且能整除 \(p - 1\) 的 \(k!\) 中的 \(k\) 不太大时，可以求出一个非平凡因子。时间复杂度是 \(O(k \log n \log k)\)。
考虑一个整数 \(b \neq p\)，那么由费马小定理 \(b^{p - 1} \equiv 1(\bmod p)\)。有\(p-1 | k!\) 有 \(b^{k!} = (b^{p-1})^q \equiv 1^q = 1(\bmod p)\)。
那么对于 \(b^{k!} \equiv m(\bmod n)\)，有 \(m = b^{k!} - nt\)，从而 \(p | m\)，因此 \((m, n)\) 是一个因子。
当 \(m \neq 0\) 时为非平凡因子。
那么我们令 \(k = 1,2,...,n\)，每次计算 \(b^{k!}\) 时逐级计算，然后判断 \((m,n)\) 是否为非 \(1\) 和 \(n\) 的数即可。
总结：没用。慢的很还有局限性。随机大法好。