Finding all the points on an elliptic curve over P(GF(16))

Question

GF(16) is constructed using p(x) = x^4+x+1 and let β = x (mod p(x)). E is the elliptic curve over P(GF(16)) that satisfies y^2 + xy = x^3+(β^4)x^2+1. How do you figure out all the points on E?

Is it sufficient to solve y^2 + xy = x^3+(β^4)x^2+1 over the integers, in which case (-1,0), (-1,1), (0,1), (0,-1), (9,-44) and (9,35) are the points?

Answer 1

$k = \Bbb{F}_2[\beta]/(\beta^4+\beta+1)$ is the field with 16 elements. 14 of its elements are not represented by integers.

Your affine elliptic curve is $$E = \{ (x,y)\in k^2, y^2+xy=x^3+\beta^4 x^2+1\}$$ and I guess you want to look at its projective closure $$C=\{ [x:y:z]\in \Bbb{P}^2(k), zy^2+zxy=x^3+\beta^4 zx^2+z^3\}$$ You can try all the $(16^3-1)/15$ points by hand, or use a CAS such as http://magma.maths.usyd.edu.au/calc/

 k<b> := GaloisField(16);
 b^4+b+1 eq 0;
 C := EllipticCurve([k|1,-b^4,0,0,1]);
 Points(C);