# 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$$次