Euler伪素数和Solovay-Stassen素性检验

nn对基bb的Euler伪素数

nn为奇合数,(b,n)=1\left(b,n\right)=1bn12(bn)(modn)b^{\frac{n-1}{2}}\equiv \left(\frac{b}{n}\right)\left(\mod n\right)

  • nn对基bb的Euler伪素数,则nn对基bb的伪素数

Solovay-Stassen素性检验

  • STEP1: 随机选取整数b,2bn2b,2\leq b\leq n-2和安全参数tt

  • STEP2: 计算rbn12(modn)r\equiv b^{\frac{n-1}{2}}\left(\mod n\right)

  • STEP3: r1r\not=1rn1r\not= n-1,则nn为合数

  • STEP4: 计算s=(bn)s=\left(\frac{b}{n}\right)

  • STEP5: rsr\not= s,则nn为合数

  • STEP6: 重复tt

最后更新于

这有帮助吗?