2
$\begingroup$

Let me ask one question. Maybe, you know an answer. Thanks in advance for any response.

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$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Of course if there is a small torsion subgroup of your rational curve, you should divide that subgroup order out of finite field curve group unless it trivialises in the finite field.

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}$

Improve this answer
$\endgroup$
5
  • $\begingroup$ Daniel S, thanks for your answer. How long does this brute force last? It must be of polynomial time. $\endgroup$
    – Dimitri Koshelev
    Commented Mar 22 at 12:28
  • $\begingroup$ @DimitriKoshelev See my edit above. The computation is more than practical as a one-off. $\endgroup$
    – Daniel S
    Commented Mar 22 at 12:34
  • $\begingroup$ Maybe, there are some strict mathematical estimates for running time of the given generation process. I need to refer to them in my future article if I decide to write it. $\endgroup$
    – Dimitri Koshelev
    Commented Mar 22 at 12:41
  • $\begingroup$ 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 $\endgroup$
    – Daniel S
    Commented Mar 22 at 13:07
  • $\begingroup$ 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. $\endgroup$
    – Dimitri Koshelev
    Commented Mar 22 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.