python - 在 Python 中实现 Miller-Rabin 复合性时遇到问题

Question

我不确定这是否是发布此问题的正确位置，因此如果不合适请告诉我!我正在尝试用 python 实现 Miller Rabin 测试。测试的目的是找到第一个见证 N(奇数)的合数。我的代码适用于长度稍小的数字，但当我输入一个巨大的数字时停止工作。 (“挑战”想要找到 N := 14779897919793955962530084256322859998604150108176966387469447864639173396414229372284183833167 的见证人，其中我的代码返回它是素数它不是)测试的第一部分是将 N 转换为 2^k + q 的形式，其中q 是素数。 python 是否有一些限制不允许使用巨大的数字？ 这是我测试该部分的代码。

def convertN(n): #this turns n into 2^x * q
placeholder = False
list = []
#this will be x in the equation
count = 1
while placeholder == False:
    #x = result of division of 2^count
    x = (n / (2**count))
    #y tells if we can divide by 2 again or not
    y = x%2
    #if y != 0, it means that we cannot divide by 2, loop exits
    if y != 0:
        placeholder = True
        list.append(count) #x
        list.append(x)     #q
    else:
        count += 1
#makes list to return
#print(list)
return list

实际测试的代码:

def test(N):
#if even return false
if N == 2 | N%2 == 0:
    return "even"
#convert number to 2^k+q and put into said variables
n = N - 1
nArray = convertN(n)
k = nArray[0]
q = int(nArray[1])
#this is the upper limit a witness can be 
limit = int(math.floor(2 * (math.log(N))**2))

#Checks when 2^q*k = 1 mod N
for a in range(2,limit):
    modu = pow(a,q,N)
    for i in range(k):
        print(a,i,modu)
        if i==0:
            if modu == 1:
                break
        elif modu == -1:
            break
        elif i != 0:
            if modu == 1:
                #print(i)
                return a
        #instead of recalculating 2^q*k+1, can square old result and modN that.
        modu = pow(modu,2,N)

如有任何反馈，我们将不胜感激!

Answer 1

我不喜欢没有答案的问题，所以我决定提供一个小更新。 事实证明我从一开始就输入了错误的号码。除此之外，我的代码应该不测试它何时等于 1，而是测试它是否等于第二部分的 -1。 用于检查的固定代码

#Checks when 2^q*k = 1 mod N
for a in range(2,limit):
    modu = pow(a,q,N)
    witness = True #I couldn't think of a better way of doing this so I decided to go with a boolean value. So if any of values of -1 or 1 when i = 0 pop up, we know it's not a witness.
    for i in range(k):
        print(a,i,modu)
        if i==0:
            if modu == 1:
                witness = False
                break
        elif modu == -1:
            witness = False
            break
        #instead of recalculating 2^q*k+1, can square old result and modN that.
        modu = pow(modu,2,N)
    if(witness == True):
        return a