Coefficients of Elliptic Curve over Finite Fields

Question

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

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

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. — SEJPM♦, Apr 21 at 18:08

Conrado · Accepted Answer · 2020-04-22 19:00:26Z

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

1 Answer 1