# Is it possible to generate an elliptic curve (with the hard discrete logarithm problem) by iterating only a finite field, but not its $j$-invariant?

Let's fix an elliptic curve $$E$$ over the field $$\mathbb{Q}$$ of rationals without complex multiplication, i.e., its endomorphism ring is just the ring $$\mathbb{Z}$$ of integers. I want to generate an elliptic curve with the same $$j$$-invariant over an arbitrary finite prime field $$\mathbb{F}_p$$ of some cryptographic size, typically ~$$256$$ bits. And as usual, the points group $$E(\mathbb{F}_p)$$ must contain a large prime subgroup of little cofactor. Of course, we cannot use the complex multiplication method to find such a curve. Is it possible to find it by iterating only $$p$$ (not $$j$$) for a long, but realistic time? Seemingly, in the classical standards on ECC such as NIST's one the two values $$p$$, $$j$$ were simultaneously iterated to find a desired curve more rapidly. I need to keep the $$j$$-invariant, because my curve $$E/\mathbb{Q}$$ has very interesting properties useful in ECC that are induced to $$E/\mathbb{F}_p$$ regardless of a concrete prime $$p$$.

Yes, this is straightforward enough. Write down you elliptic curve with coefficients in $$\mathbb Q$$. For any $$p$$ you can then use the same equation with the coefficients interpreted as elements of $$\mathbb F_p$$. It is then highly feasible to count the number of points on this curve over the prime field using the Schoof-Elkies-Atkin algorithm and then testing the resulting point count for primality.
ETA: Note that we believe that SEA will run in time $$O(\log^4 p)$$ and would perhaps expect to run it maybe a couple of hundred times to find a curve with prime order with $$p\approx 2^{256}$$
• The heuristic estimate in SEA is that roughly half of the small primes $\ell$ are Elkies primes with respect to $p$. It might be that this can be established for almost all $p$. If you want to avoid this heutirtic, then the naive Schoof algorithm can be perfromed in time roughly $\log^5p$: en.wikipedia.org/wiki/Schoof%27s_algorithm#Complexity Mar 22 at 13:07
• Mathematically speaking, I need any answer to the following question: What is the average proportion of prime order reductions at primes $p$ of ~$256$ bits if $E/\mathbb{Q}$ is a torsion-free fixed elliptic curve? If this proportion is quite large, then we actually can find a desired curve $E/\mathbb{F}_p$ by using the SEA algorithm. Mar 22 at 13:18