强伪素数和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$