# Elliptic curve with prime subgroup equal to field size

I am aware that when the equation $$\#E(\mathbb{Z}_p) = p$$ holds for prime $$p$$, the elliptic curve is called "anomalous" and is insecure do to "Smart's attack".

Consider the similar case that $$E(\mathbb{Z}_p)$$ has a proper subgroup of (prime) order $$p$$, so $$p \neq \#E$$. In this case $$p$$ divides $$\#E$$ and $$\#E > p$$. This relationship of the (sub)group order matching the field size (thus forcing primality) is desirable for some applications.

Is such a curve secure for the discrete log performed in the $$p$$-order subgroup, or is this vulnerable to a similar attack? What would be the process to generate such a curve that is arguably safe for cryptographic use?

From what I read, curves over $$GF(2^n)$$ for some $$n$$ are less stable. But analogously, for $$E(GF(2^n))$$ there could be a subgroup of order $$2^n$$ and as long as $$2^n$$ has a large prime factor it should be safe for the discrete log. Is this also a possibility?

• "As long as $2^n$ has a large prime factor" - $2^n$ never has a large prime factor... – poncho Aug 13 '19 at 14:38

It seems that curves like that do not exist.

Hasse's bound states that $$|N-(p+1)| \le 2\sqrt p$$, where $$N=\#E$$. Writing the order of the group as $$N = ph$$, you get:

$$|ph-(p+1)| \le 2\sqrt p \rightarrow$$

$$|p(h-1)-1)| \le 2\sqrt p \rightarrow$$

$$|\sqrt p(h-1)-\frac{1}{\sqrt p}| \le 2$$

The only way this inequality is true for $$p > 5$$ is if $$h = 1$$, i.e., $$\#E=p$$.

• The curve $y^2=x^3+3x$ over $\mathbb F_5$ has $10$ rational points. (This is the only counterexample.) – yyyyyyy Aug 13 '19 at 13:03