美文网首页
Miller-Rabin素数测试

Miller-Rabin素数测试

作者: tdeblog | 来源:发表于2016-06-27 17:04 被阅读0次

    费马小定理:对于素数p和任意整数a,有ap ≡ a(mod p)(同余)。反过来,满足ap ≡ a(mod p),p也几乎一定是素数。
    伪素数:如果n是一个正整数,如果存在和n互素的正整数a满足 an-1 ≡ 1(mod n),我们说n是基于a的伪素数。如果一个数是伪素数,那么它几乎肯定是素数。
    Miller-Rabin测试:不断选取不超过n-1的基b(s次),计算是否每次都有bn-1 ≡ 1(mod n),若每次都成立则n是素数,否则为合数。

    Function Miller-Rabin (n : longint) :boolean;
    begin
        for i := 1 to s do
        begin
            a := random(n - 2) + 2;
            if mod_exp(a, n-1, n) <> 1 then return false;
        end;
        return true;
    end;
    

    相关文章

      网友评论

          本文标题:Miller-Rabin素数测试

          本文链接:https://www.haomeiwen.com/subject/obwzdttx.html