最后更新于3年前
nnn为奇合数，(b,n)=1\left(b,n\right)=1(b,n)=1，n−1=2stn-1=2^s tn−1=2st，ttt为奇数，bt≡1(mod n)b^t\equiv 1\left(\mod n\right)bt≡1(modn)或存在0≤r<s0\leq r<s0≤r<s使得b2rt≡−1(mod n)b^{2^r t}\equiv -1\left(\mod n\right)b2rt≡−1(modn)
存在无穷个对基222的强伪素数
若nnn对基b(1≤b≤n−1)b\left(1\leq b\leq n-1\right)b(1≤b≤n−1)的强伪素数可能性至多为2525%25
STEP1: 安全参数kkk，n−1=2st,tn-1=2^s t,tn−1=2st,t为奇数STEP2: 随机选取整数b,2≤b≤n−2b,2\leq b\leq n-2b,2≤b≤n−2STEP3: 计算r0≡bt(mod n)r_0\equiv b^{t}\left(\mod n\right)r0≡bt(modn)若r0=1r_0=1r0=1或r0=n−1r_0=n-1r0=n−1，则通过检验，可能为素数。回到第二步否则进入下一步STEP3: 计算r1≡r02(mod n)r_1\equiv r_{0}^{2}\left(\mod n\right)r1≡r02(modn)若r1=n−1r_1=n-1r1=n−1，则通过检验，可能为素数。回到第二步否则进入下一步STEP4: 计算r2≡r12(mod n)r_2\equiv r_{1}^{2}\left(\mod n\right)r2≡r12(modn)⋯\cdots⋯STEPs+1: 计算rs−1≡rs−22(mod n)r_{s-1}\equiv r_{s-2}^{2}\left(\mod n\right)rs−1≡rs−22(modn)若rs−1=n−1r_{s-1}=n-1rs−1=n−1，则通过检验，可能为素数。回到第二步否则nnn为合数kkk次测试后，nnn为合数的概率为0.25k{0.25}^k0.25k
STEP1: 安全参数kkk，n−1=2st,tn-1=2^s t,tn−1=2st,t为奇数
STEP2: 随机选取整数b,2≤b≤n−2b,2\leq b\leq n-2b,2≤b≤n−2
STEP3: 计算r0≡bt(mod n)r_0\equiv b^{t}\left(\mod n\right)r0≡bt(modn)
若r0=1r_0=1r0=1或r0=n−1r_0=n-1r0=n−1，则通过检验，可能为素数。回到第二步
否则进入下一步
STEP3: 计算r1≡r02(mod n)r_1\equiv r_{0}^{2}\left(\mod n\right)r1≡r02(modn)
若r1=n−1r_1=n-1r1=n−1，则通过检验，可能为素数。回到第二步
STEP4: 计算r2≡r12(mod n)r_2\equiv r_{1}^{2}\left(\mod n\right)r2≡r12(modn)
⋯\cdots⋯
STEPs+1: 计算rs−1≡rs−22(mod n)r_{s-1}\equiv r_{s-2}^{2}\left(\mod n\right)rs−1≡rs−22(modn)
若rs−1=n−1r_{s-1}=n-1rs−1=n−1，则通过检验，可能为素数。回到第二步
否则nnn为合数
kkk次测试后，nnn为合数的概率为0.25k{0.25}^k0.25k