数学-数论-Miller_Rabin算法

Posted by

定义

Miller_Rabin算法是一种随机化素数测试算法。

有关概念

  1. 费马小定理的逆命题:若\(a^{p-1}\equiv1\quad(mod~p)\),则\(p\)是质数。
    这个命题是假命题,但是错误概率不大,大约为\(\frac 14\),我们称这样的\(p\)是伪素数。

  2. 二次探测定理:如果\(p\)是一个质数,那么对于\(x(0 < x < p)\),若\(x^2\equiv1\quad(mod~p)\),则\(x=1或x=p−1\)。

求解算法

思路与简单证明

根据费马小定理的逆命题,我们可以多次随机\(a\)来测试\(p\)是否是质数。
为了提高测试效率,我们加上二次探测定理:
将\(p-1\)表示为\(2^r\cdot k\),对于\({(a^k)}^{2^i}(1\leq i\leq r)\),若它对\(p\)取模等于\(1\),我们判定\({(a^k)}^{2^{i-1}}\)是否等于\(\pm 1\),来测试\(p\)是否是质数。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注