最后更新于3年前
nnn为奇合数，(b,n)=1\left(b,n\right)=1(b,n)=1，bn−12≡(bn)(mod n)b^{\frac{n-1}{2}}\equiv \left(\frac{b}{n}\right)\left(\mod n\right)b2n−1≡(nb)(modn)
若nnn对基bbb的Euler伪素数，则nnn对基bbb的伪素数
STEP1: 随机选取整数b,2≤b≤n−2b,2\leq b\leq n-2b,2≤b≤n−2和安全参数tttSTEP2: 计算r≡bn−12(mod n)r\equiv b^{\frac{n-1}{2}}\left(\mod n\right)r≡b2n−1(modn)STEP3: 若r≠1r\not=1r=1且r≠n−1r\not= n-1r=n−1，则nnn为合数STEP4: 计算s=(bn)s=\left(\frac{b}{n}\right)s=(nb)STEP5: 若r≠sr\not= sr=s，则nnn为合数STEP6: 重复ttt次
STEP1: 随机选取整数b,2≤b≤n−2b,2\leq b\leq n-2b,2≤b≤n−2和安全参数ttt
STEP2: 计算r≡bn−12(mod n)r\equiv b^{\frac{n-1}{2}}\left(\mod n\right)r≡b2n−1(modn)
STEP3: 若r≠1r\not=1r=1且r≠n−1r\not= n-1r=n−1，则nnn为合数
STEP4: 计算s=(bn)s=\left(\frac{b}{n}\right)s=(nb)
STEP5: 若r≠sr\not= sr=s，则nnn为合数
STEP6: 重复ttt次