小编Max*_*ell的帖子

今天一直试图实施Rabin-Miller Strong Pseudoprime Test.

使用Wolfram Mathworld作为参考,第3-5行总结了我的代码.

然而,当我运行程序时,它(有时)说素数(甚至低,如5,7,11)不是素数.我已经查看了很长一段时间的代码,无法弄清楚出了什么问题.

为了帮助我看了这个网站以及许多其他网站,但大多数使用另一个定义(可能相同,但因为我是这种数学的新手,我看不到相同的明显连接).

我的代码:

import random

def RabinMiller(n, k):

    # obviously not prime
    if n < 2 or n % 2 == 0:
        return False

    # special case        
    if n == 2:
        return True

    s = 0
    r = n - 1

    # factor n - 1 as 2^(r)*s
    while r % 2 == 0:
        s = s + 1
        r = r // 2  # floor

    # k = accuracy
    for i …