伪素数和Fermat素性检验

判断素数

$n$为素数$\Longleftrightarrow$对任意$b,\left(b,n\right)=1$，$b^{n-1}\equiv 1\left(\mod n\right)$或${\mathrm{ord}}_{n}{\left(b\right)}\mid n-1$

$n$对基$b$的伪素数

$n$为奇合数，$\left(b,n\right)=1$，$b^{n-1}\equiv 1\left(\mod n\right)$

• 存在无穷个对基$2$的伪素数

• 若$n$为对基$b_1,b_2$的伪素数，则$n$为对基$b_1\cdot b_2$的伪素数

• 若$n$为对基$b$的伪素数，则$n$为对基$b^{-1}$的伪素数

• 若存在$b$使得$b^{n-1}\not\equiv 1\left(\mod n\right)$，则模$n$的简化剩余系中至少有一半的的数满足$b^{n-1}\not\equiv 1\left(\mod n\right)$

Fermat素性检验

• STEP1: 随机选取整数$b$和安全参数$t$

• STEP2: 计算$r\equiv b^{n-1}\left(\mod n\right)$

• STEP3: 若$r\not=1$，则$n$为合数

• STEP4: 重复$t$次

Carmichael数

合数$n$满足对任意$b,\left(b,n\right)=1$，$b^{n-1}\equiv 1\left(\mod n\right)$

存在无穷多个Carmichael数

证明$n$为Carmichael数

• STEP1: $n=p_1\cdots p_s$
• STEP2: $b^{p_i-1}\equiv 1\left(\mod p_i\right)$
• STEP3: $b^{n-1}\equiv 1\left(\mod p_i\right)$