Euler伪素数和Solovay-Stassen素性检验

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

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

• 若$n$对基$b$的Euler伪素数，则$n$对基$b$的伪素数

Solovay-Stassen素性检验

• STEP1: 随机选取整数$b,2\leq b\leq n-2$和安全参数$t$
• STEP2: 计算$r\equiv b^{\frac{n-1}{2}}\left(\mod n\right)$
• STEP3: 若$r\not=1$且$r\not= n-1$，则$n$为合数
• STEP4: 计算$s=\left(\frac{b}{n}\right)$
• STEP5: 若$r\not= s$，则$n$为合数
• STEP6: 重复$t$次