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