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

Questions

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

January 22, 2022

So I was planing on reading up on the Pollard-Rho-Algorithm to compute the discrete logarithm and decided to go have a look for a python implementation and how it is implemented. I stumbled upon this link [https://replit.com/@sidav/Pollards-Rho-Discrete-Log][1].

According to the console the program is written in Python 2.7.16. As I am using Python 3.10 i changed some stuff in the code given on this site. To specify, I added in int() casts because otherwise pow() wouldn’t work with 3 parameters and changed xrange() to range().

After doing this i ran the code on my end and the computation for the first example given: (2, 11, 59) returns the right solution. But all the other examples given in the code would return a false solution. Does anyone know why that may happen?

Below is "my" code i run on Python 3.10 with the casts i added and the original code is to be found in the link provided above.

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))