运行在 Python 3.10 环境中用 Python 2.7.16 编写的 Pollard-Rho 算法

Question

所以我打算阅读 Pollard-Rho 算法来计算离散对数，并决定去看看 python 实现及其实现方式。我偶然发现了这个 link [https://replit.com/@sidav/Pollards-Rho-Discrete-Log][1].

根据控制台，该程序是在 Python 2.7.16 中编写的。当我使用 Python 3.10 时，我更改了本网站提供的代码中的一些内容。为了具体说明，我添加了 int() 强制转换，否则 pow() 将无法使用 3 个参数并将 x运行ge() 更改为运行ge().

完成此操作后，我运行给出了第一个示例的代码和计算：(2, 11, 59) return 是正确的解决方案。但是代码中给出的所有其他示例都是 return 错误的解决方案。有谁知道为什么会这样？

下面是 Python 3.10 上我运行的“我的”代码，其中包含我添加的转换，原始代码可以在上面提供的 link 中找到。

def ext_euclid(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, xx, yy = ext_euclid(b, a % b)
        x = yy
        y = xx - (a / b) * yy
        return d, x, y


 def inverse(a, n):
    return int(ext_euclid(a, n)[1])


def xab(x, a, b, tuple):
    G, H, P, Q = tuple[0], tuple[1], tuple[2], tuple[3]

    sub = x % 3 # Subsets

    if sub == 0:
        x = x*G % P
        a = (a+1) % Q

    if sub == 1:
        x = x * H % P
        b = (b + 1) % Q

    if sub == 2:
        x = x*x % P
        a = a*2 % Q
        b = b*2 % Q
    return x, a, b

 def pollard(G, H, P):

    Q = int((P - 1) / 2)  # sub group
    x = G*H
    a = 1
    b = 1

    X = x
    A = a
    B = b

    for i in range(1, P):

        x, a, b = xab(x, a, b, (G, H, P, Q))

        X, A, B = xab(X, A, B, (G, H, P, Q))
        X, A, B = xab(X, A, B, (G, H, P, Q))

        if x == X:
            break


    nom = a-A
    denom = B-b

    res = (inverse(denom, Q) * nom) % Q

    if verify(G, H, P, res):
        return res

    return res + Q


def verify(g, h, p, x):
    return pow(g, int(x), p) == h

M = 424242

args = [
    (2, 11, 59),
    (2, M, 5041259),
    (5, M, 87993167),
    (2, M, 1726565507),
    (7, M, 24455596799),
    (5, M, 368585361623),
    (11, M, 4520967464159),
    (5, M, 66008980226543),
    (5, M, 676602320278583),
    (2, M, 2075952270932339),
    (7, M, 21441211962585599)
]

for arg in args:
    res = pollard(*arg)
    print (arg, ': ', res)
    print ("Validates: ", verify(arg[0], arg[1], arg[2], res))
    print

A = 25
B = 32
M = 47
res = pollard(A, B, M)
print(res)
print ("Validates: ", verify(A, B, M, res))

Answer 1

在 Python 3:

>>> 1 / 2
0.5

在 Python 2:

>>> 1 / 2
0

在 Python 3.

中，您需要使用 // 而不是 / 进行整数除法

>>> 1 // 2
0

运行在 Python 3.10 环境中用 Python 2.7.16 编写的 Pollard-Rho 算法

Running Pollard-Rho-Algorithm written in Python 2.7.16 in an Python 3.10 environment

python

python-2.7

python-3.x

运行 在 Python 3.10 环境中用 Python 2.7.16 编写的 Pollard-Rho 算法

Running Pollard-Rho-Algorithm written in Python 2.7.16 in an Python 3.10 environment

python

python-2.7

python-3.x

运行在 Python 3.10 环境中用 Python 2.7.16 编写的 Pollard-Rho 算法