# Large prime numbers in ECC and discrete logarithm

In elliptic curve cryptography using Diffie-Hellman protocol, we need to use large prime numbers.

So my question is what makes discrete logarithm hard to solve when we use large prime numbers.

I guess since we use large prime numbers we will have a lot of points that satisfy our curve equation

The answer is not so simple;

• First of all the number of points that satisfy the curve equation $$N$$ on the curve is bounded by the Hasse's bound $$|N - (q+1)| \le 2 \sqrt{q}$$ for a prime $$q$$. This simply says that if you want a curve that has a large number of points then you need a big prime ( short story).

• The curve order must be prime ( prime curves) or must have at least one large prime factor. Curve25519 is not a prime curve, that has a cofactor $$h=N/8$$, this enables Montgomery representation of the curve that helps secure implementations. If the curve has smooth order, which means it won't have a large prime then the Poglig-Helamn will destroy it regardless of order. Having a large order or a large prime order is important.

• The twist of the curve must have large prime order against twist attacks.

• The order of the curve and order of the base field $$(K)$$ are the same then the discrete logarithm on this curve runs in linear time Smart 97.

• The curve should not be supersingular, otherwise, the Discrete logarithm is easy ( now they are in use for isogeny that doesn't use discrete logarithm and expected to be secure against Shor's attack)

Now combining these we can say if the point curve group of the ECC has a large prime and doesn't have some special property ( we can say it is a generic curve) then the best attack is the Pollard's Rho with $$\mathcal{O}(\sqrt{N})$$.

With this, we can say Curve25519 has around 128-bit discrete log security, and Curve448 has 224-bit discrete log security.