First, sorry for my english which is not my natural language and secondly, I hope I am posting on the right section.
So let's explain my problem.
I am trying to implement the Pohlig-Hellman algorithm based on elliptic curves with the Baby-Steps-Giant-Steps for each iteration.
My Python implementation use a curve on finite field with a smooth prime modulus $N = 2*853*3593*4339$.
With the curve : $y^2 = x^3 + 521x + 1331$ on $\mathbb{F}_{26596586063}$
And the generator $G = (20197258757, 24233149744)$
In theory, and if I understand correctly, the worst complexity in the Baby-Steps-Giant-Steps phase will be $\sqrt{4339}$, right ?
My implementation seems to work (I have the right solution) but I don't have the right complexity : the Polhig-Hellman problem reduction seems useless because I have the same complexity with the Baby-Steps-Giant-Steps running alone.
When I try to solve the discrete logarithm : $H = xG$, my implementation run with a complexity of : $O(\sqrt{x})$ approximatly.
I don't understand my mistake and I am very confuse...
Thanks for your answer.
Here is my implementation (in Python):
def baby_step_giant_step(curve, G, H, order):
m = int(math.ceil(gmpy2.sqrt(order)))
L = {}
# Baby steps
for j in range(0, m):
P_tmp = curve.mul(j, G)
L[str(P_tmp)] = j
mG = curve.mul(m, G)
# Giant steps
for i in range(0, m):
P_tmp = curve.mul(i, mG)
if not P_tmp.isInf():
P_tmp = ecc.Point(P_tmp.x, (-P_tmp.y) % curve.p)
P = curve.add(H, P_tmp)
index = str(P)
if index in L:
return (L[index] + i*m) % curve.p
return None
# Solve the equation : G^x = H (mod curve.p)
def pohlig_hellman(curve, G, H):
N = curve.p-1
factors = decompose_order(N)
x = 0
for i in range(len(factors)):
ni = factors[i][0]**(factors[i][1])
tmp = N//ni
G_prime = curve.mul(tmp, G)
H_prime = curve.mul(tmp, H)
# Now, use the Baby Step Giant Step algorithm to solve :
# H_prime = x_prime*G_prime
x_prime = baby_step_giant_step(curve, G_prime, H_prime, ni)
while x_prime == None:
order *= 2
x_prime = baby_step_giant_step(curve, G_prime, H_prime, ni)
# Use the CRT to solve the equation x_prime = x (mod ni)
(gcd, x0, x1) = xgcd(ni, tmp)
x += x_prime*x1*tmp
return x % N
# (A, B, N)
curve = ecc.Curve(521, 1331, 26596586063)
G = ecc.Point(20197258757,24233149744)
H = curve.mul(523151, G)
x = pohlig_hellman(curve, G, H)
print("x = %s" % x)
PS : don't be afraid by the WHILE loop, it was only for debuging purpose.