1
$\begingroup$

In many articles i have found directly the calculation of prime elliptic curve. How can i calculate this prime $p$ ? For example if I consider NIST P-256, $ p = 2^{256}-2^{224}+2^{192}+2^{96}-1$. Why ? Is there a formula ? Thanks for your support.

$\endgroup$
2
$\begingroup$

This prime $p$ corresponds to the size on the base field $\mathbb F_p$ on which is defined the elliptic curve. It has not been computed, it has been chosen. It is chosen to satisfy a few properties, like, of course, being prime, but also being large enough (here, 256 bits), and allowing fast computations modulo $p$. Maybe when you say "prime elliptic curve", you mean elliptic curves with a prime number of points? The number of points is not the prime $p$, and is computed using the Schoof-Elkies-Atkin algorithm.

$\endgroup$
  • $\begingroup$ I understand that $p$ is the size of $\mathbb{F}_{p}$. Ok but why $ p = 2^{256}-2^{224}+2^{192}+2^{96}-1$ and not for example only $p=2^{256}$ ? Why are there $2^{224}+2^{192}+2^{96}$ ? (I don't understand the last calculation. Why $-1$ and not $+1$ ? $\endgroup$ – Ellipticat Sep 20 '14 at 9:43
  • $\begingroup$ Because $p$ has to be a prime number. $2^{256}$ is definitely not a prime number (even though there is a field of order $2^{256}$, we don't want to use it). Same answer for +1, if you replace -1 with +1, the result is not a prime number. $\endgroup$ – Calodeon Sep 20 '14 at 10:33
  • $\begingroup$ As they said $p$ is chosen to fill some conditions: to be prime and to allow fast computation modulo $p$. A good explaination could be found in this post: imperialviolet.org/2010/12/04/ecc.html $\endgroup$ – ddddavidee Sep 20 '14 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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