Elliptic curve point counting over finite fields with Gaussian normal basis (Q1418381)

This short note describes an improvement on \textit{P. Gaudry's} article [Advances in cryptology - ASIACRYPT 2002, 311--327 (2002; Zbl 1065.11098)] for point counting on elliptic curves over binary fields. The method stems from \textit{T. Satoh} [J. Ramanujan Math. Soc. 15, 247--270 (2000; Zbl 1009.11051)] and the improvement in \textit{T. Satoh}, \textit{B. Skjernaa}, and \textit{Y. Taguchi} [Finite Fields Appl. 9, 89--101 (2003; Zbl 1106.14302)] combined with the AGM method due to Mestre. The authors propose to use a Gaussian normal basis representation to allow an efficient computation of the norm and show that the basis can also be used for the \(p\)-adic fields one lifts to. This approach leads to faster implementations if there exists a basis of type \(1\) or \(2\) as this allows to multiply efficiently.