博主是初学初等数论（整除+同余+原根），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。 我整理成一个系列：初等数论，方便检索。

费马小定理，对于 a ∈ Z , p a\in Z,p a∈Z,p为素数,有 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1(mod p) ap−1≡1(modp)

这是由已知素数推公式，那么如果已有公式呢？能推测p就一定是素数吗？这就是费马素性检测算法要告诉我们的内容，p是素数的概率。

伪素数：如果 n n n是奇合数，对于 b ∈ Z , b\in Z, b∈Z,有 b n − 1 ≡ 1 ( m o d n ) , b^{n-1}\equiv 1(mod n), bn−1≡1(modn),那么称 n n n是对于基 b b b的伪素数。(伪素数不能单独存在，一定是针对某一个基成立的性质)

算法流程： 给定某一奇整数 n ≥ 3 n\ge 3 n≥3和安全参数 k k k，即检测不超过 k k k次。

我有一个问题还没有解决，为什么是 1 2 k , \frac1{2^k}, 2k1​,素数合数的分布是不均匀的，为什么能用 1 2 \frac{1}{2} 21​来考虑呢？

答案来源于 Cryptography Theory and Practice