Finding points and encoding messages on elliptic curves over characteristic 2

While fast probabilistic algorithms for finding points on elliptic curves over finite fields are well-known, the problem of derandomizing these algorithms is not so well studied. For elliptic curves over fields of characteristic two, we give an algorithm for finding a point in deterministic polynomial time. We also extend the algorithm to the encoding problem, so that now messages can be encoded on such curves in deterministic time for use in elliptic curve cryptography, in particular the ECC analog of Massey-Omura.