On the CM character of the curves \(y^ 2=x^ q-1\) (Q1356235)

The author gives a formula for the number of points on the hyperelliptic curve \[ y^2=x^q-1 \] over a field of \(p\) elements. This is done by determining the CM character of the curve and is similar to the method of Gauss in the elliptic curve case of \(q=3\). The resulting algorithm depends on decomposing the prime \(p\) in the \(q\)th cyclotomic field. The author points out that this can be done in probabilistic polynomial time or in deterministic polynomial time if one is willing to assume the Extended Riemann Hypothesis.