> 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/qiang-wei-su-shu-he-millerrabin-primality-su-xing-jian-yan.md).

# 强伪素数和Miller-Rabin Primality素性检验

## $$n$$**对基**$$b$$**的强伪素数**

$$n$$为奇合数，$$\left(b,n\right)=1$$，$$n-1=2^s t$$，$$t$$为奇数，$$b^t\equiv 1\left(\mod n\right)$$或存在$$0\leq r\<s$$使得$$b^{2^r t}\equiv -1\left(\mod n\right)$$

* 存在无穷个对基$$2$$的强伪素数
* 若$$n$$对基$$b\left(1\leq b\leq n-1\right)$$的强伪素数可能性至多为$$25%$$

## **Miller-Rabin Primality素性检验**

> * **STEP1:** 安全参数$$k$$，$$n-1=2^s t,t$$为奇数
> * **STEP2:** 随机选取整数$$b,2\leq b\leq n-2$$
> * **STEP3:** 计算$$r\_0\equiv b^{t}\left(\mod n\right)$$
>   * 若$$r\_0=1$$或$$r\_0=n-1$$，则通过检验，可能为素数。回到第二步
>   * 否则进入下一步
> * **STEP3:** 计算$$r\_1\equiv r\_{0}^{2}\left(\mod n\right)$$
>   * 若$$r\_1=n-1$$，则通过检验，可能为素数。回到第二步
>   * 否则进入下一步
> * **STEP4:** 计算$$r\_2\equiv r\_{1}^{2}\left(\mod n\right)$$
>
>   $$\cdots$$
> * **STEPs+1:** 计算$$r\_{s-1}\equiv r\_{s-2}^{2}\left(\mod n\right)$$
>   * 若$$r\_{s-1}=n-1$$，则通过检验，可能为素数。回到第二步
>   * 否则$$n$$为合数
>
>     $$k$$次测试后，$$n$$为合数的概率为$${0.25}^k$$