Why your elliptic curve needs a large prime order subgroup

The idea is to factor the order of $E(F_q)$ into a product of prime powers, solve the ECDLP into smaller subgroups and reconstruct the answer into our original group using the Chinese Remainder Theorem (CRT).

Take a generator of $E(F_q)$ , say $P$ . We want to solve $Q = kP$ . Since we know the order of $E(F_q)$ , we can decompose it to prime-power factors. First, we will solve ("find $k$ ") this ECDLP instance into those smaller pairwise-prime order subgroups. Then, using the CRT, we will get our final answer for $k$ in the original group.

Note that solving the ECDLP into those much smaller and tractable subgroups can run in parallel.

As an example, we define a curve over $F_{1021}$ , which has order 966 and for which we compute its prime factor decomposition:

F = GF(1021)
E = EllipticCurve(F, [905, 100])
P = E(1006, 416) # curve generator
Q = E(612, 827) # we want to solve for k in Q = kP
E_order = E.order()
assert E_order == 966

primes = prime_factors(E.order())
assert primes == [2, 3, 7, 23]

Now, we define a helper function to solve the ECDLP in each of our subgroups:

def solve_ecdlp_in_smaller_subgroup(P, Q, cofactor):
    # map P and Q into smaller subgroup
    P_prime = cofactor * P
    Q_prime = cofactor * Q
    
    # solve an "easier" discrete log, uses the baby-step giant-step algorithm by default
    k = discrete_log(Q_prime, P_prime, operation='+')
    return k

We will store our residues and modulis for each of the ECDLP that we will solve:

residues = []
modulis = []

# map P and Q to smaller subgroups and solve ECDLP there
for p in primes:
    cofactor = E_order / p
    k = solve_ecdlp_in_smaller_subgroup(P, Q, cofactor)
    residues.append(k)
    modulis.append(p)

And that's why you want your curve to have the largest subgroup prime order possible: the complexity of solving the ECDLP is the complexity of solving the ECDLP in the largest subgroup (23 here)!

Using the chinese remainder theorem, we can now compute $k$ :

k = CRT(residues, modulis)
assert k * P == Q # True

Why your elliptic curve needs a large prime order subgroup

Resources