1
$\begingroup$

When talking about elliptic curve over finite fields in ECC, we often assume that the elliptic curve can be written in the Weierstrass form

$$y^2=x^3+Ax+B, \quad A,B\in \mathbb{F}_q$$.

where $\mathbb{F}_q$ is a field of characteristic not $2$ and $3$. (For example, Schoof's algorithm to compute $\#E(\mathbb{F}_q)$ assumes this. )

  1. In practice, would $A$ and $B$ ever be non-integer coefficients(suppose we are working over $q=p^n$)? That is to say $A=\underbrace{1+...+1}_{\text{sum of }1}$ or might we pick $A,B$ to be other elements from $\mathbb{F}_q$?

  2. How would these algorithms that assume the Weierstrass model, generalize to say elliptic curves over fields of characteristic $2$ or $3$? For example, Koblitz curves are a class of elliptic curves of the form $y^2+xy=x^3+ax+1$ in $\mathbb{F}_{2^m}$?

$\endgroup$
  • 1
    $\begingroup$ Note that $A$ and $B$ have to be field elements or they have an equivalent representation as a field element. Therefore there cannot be a non-integer $A$ or $B$ if you're using an integer-based field like $\mathbb F_p$. Of course if you use $\mathbb F_q$ for some $q=p^n$ then you're usually using polynomials anyways but still have some "integer encoding" of them for computer representation. $\endgroup$ – SEJPM Apr 21 at 18:08
1
$\begingroup$
  1. $A$ and $B$ can be non-integers if you're working with an extension field. For example, this happens with pairing-friendly curves where you need to work with elliptic curves over e.g. $\mathbb{F}_{p^2}$.
  2. Depends on the algorithm. For counting elliptic curve points, the "hard" part is computing $\#E(\mathbb{F}_p)$. If you compute that, than it's easy to compute $\#E(\mathbb{F}_{p^k})$; see this answer. In the Koblitz curve case it's even easier since computing $\#E(\mathbb{F}_{2})$ is trivial (it's either 2 or 4 depending on the curve).
| improve this answer | |
$\endgroup$

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.