An algorithm to compute the number of points on elliptic curves of \(j\)-invariant 0 or 1728 over a finite field (Q1313211)

The authors present ``an algorithm to compute the number of \(\mathbb{F}_ q\)- rational points on elliptic curves defined over a finite field with \(j\)- invariant 0 or 1728''. Since they assume that a non-square modulo the characteristic \(p\) is given a priori, this is rather easy: it suffices to compute a gcd in the rings \(\mathbb{Z} [\zeta_ 3]\) and \(\mathbb{Z}[i]\), respectively. In this way one finds the ideal generated by the Frobenius endomorphism. The problem is now to find the correct generator. This is cleverly avoided by the authors by simply computing all generators and they leave the problem to the reader. So, the running time \(O(\log^ 3q)\) claimed by the authors, is merely the time spent doing the gcd algorithm. The essential part of the presented ``algorithm'' is, of course, very well known and has been exposed in more efficient and elegant ways [for instance by \textit{G. Cornacchia}, Su di un metodo per la risoluzione in numeri interi dell'equazione \(\sum^ n_{h=0} C_ hx^{n-h} y^ h=P\), Giorn. Mat. Battaglini 46, 33-90 (1908; JFM 39.0258.02) but also in recent textbooks].