> For the complete documentation index, see [llms.txt](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/su-xing-jian-yan/euler-wei-su-shu-he-solovaystassen-su-xing-jian-yan.md).

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