算法
记号
\(a \mod p\)：\(a\) 除 \(p\) 的余数，等于 \(a - p \times \lfloor \frac{a}{p} \rfloor\)。
\(a \mid b\)：\(a\) 整除 \(b\) 即\(a\) 是 \(b\) 的因数。
素数判定
试除法
对于任意整数 \(n\)，它的因数 \(d,\frac{n}{d}\) 总是成对出现，所以可以枚举 \([2,\sqrt{n}]\) 内的数，逐一判断是不是 \(n\) 的因数即可。
费马素性测试
属于概率性测试，根据费马小定理实现。
对于任意整数 \(n\)，从 \([2,n-1]\) 中取数 \(a\) 作为基，如果满足 \(a^{n-1}\equiv 1(\mod n)\)，则通过这一轮测试，如果所有测试均通过，那么认为 \(n\) 是一个素数。
Miller-Rabin 素性测试
定理
威尔逊定理及其扩展
\((p-1)!\equiv -1\ (mod\ p), p \in prime\)