Pohlig-Hellman and Shanks algorithm on ECC

Question

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.

Answer 1

Although I was not able to run the scripts (perhaps my fault, my Python skills are mediocre at best), let me try to elaborate (slightly) on fkraiem's comment.

You are indeed right that the complexity of Pohlig-Hellman is lower than the complexity of BSGS (for a curve of smooth order). However, your parameters are relatively small. Looking at the definition of the big-$O$ notation, we see that this line of reasoning will ignore some constants. That is, roughly, the complexity $O(\sqrt{x})$ means that there is some constant $c$ such that for large parameters the complexity will be $\leq c\sqrt{x}$. This is however only a statement about large parameter values, and does not have much meaning for specifically chosen (small) parameters. For example a situation where an algorithm with complexity $O(t)$ is slower than an algorithm with complexity $O(t^2)$ for a specific instance is easily possible. Note that the definitions of small and large here depend very much on context.

Having said that, I am not sure whether that is actually the problem here. Iirc Pohlig-Hellman does not behave very poorly for small parameters, nor does BSGS. Perhaps you should be careful how you are measuring your complexity. Is it running time, number of curve operations, number of field multiplications, etc.? It could be that there is some overhead unrelated to the algorithm which affects the complexity.

Edit: Okay, there are some confusing parts in your question. Let's get the details straight. We are assuming a curve $E:y^2=x^3+521x+1331$ over the field $\mathbb{F}_{26596586063}$. As you say, the points on this curve form a group of order $N=2*853*3593*4339$, with some generator $G$. Suppose there is some $H\in E$ such that $H=\ell G$ for $\ell\in[1,..,N]$. I deliberately name the scalar $\ell$ as opposed to $x$ to avoid confusion with the curve variable $x$. Let's compare the two ways in which we can solve this DLP (with a bit of abuse of notation):

1. BSGS: Doing BSGS on a group of order $N$ has complexity $O(\sqrt{N})$ and will give us $\ell\pmod{N}$.
2. Pohlig-Hellman: Doing PH will cut the DLP up into four parts. We solve four smaller DLP's with respective complexities $O(\sqrt{2})$, $O(\sqrt{853})$, $O(\sqrt{3593})$ and $O(\sqrt{4339})$ (these are your $ni$'s), to get $\ell\pmod{2}$, $\ell\pmod{853}$, $\ell\pmod{3593}$ and $\ell\pmod{4339}$. We then use the CRT to recover $\ell\pmod{N}$. Hence we have complexity $O(\sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339})$ for the small DLP's. Note that we are forgetting about the cost to actually reduce to these small-order DLP's.

What we conclude is that for BSGS we have a complexity of around $\sqrt{N}\approx 163085$ while for Pohlig-Hellman we only have a complexity of around $\sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339}\approx 156$.