Counting points on genus-3 hyperelliptic curves with explicit real multiplication (Q6165852)

This paper proposes a probabilistic algorithm, with polynomial complexity, to compute the zeta function (and therefore the cardinal) of a genus-3 hyperelliptic curve \(\mathcal{C}\),\, defined over a finite field \(\mathbb{F}_q\),\, given by a Weiertrass equation of degree 7 and endowed with an explicit real multiplication, that is to say with an endomorphism \({\eta}\in\mathrm{End}(\mathrm{Jac}(\mathcal{C}))\)\, such that the ring \(\mathbb{Z}[\eta]\)\, is isomorphism to an order in a totally real cubic field with the action of \(\eta\)\, given by explicit polynomials. The computational complexity of the proposed algorithm is \(\tilde{O}((\log q)^6)\)\, bits, where the implicit constant only depends.on \(\mathbb{Z}[\eta]\)\, and the degree of the polynomials defining \(\eta\). The authors points out that the point-counting algorithm can be adapted \lq \lq for general genus-3 hyperelliptic curves (i.e., without RM) with complexity \(\tilde{O}((\log q)^{14})\)''. The algorithm follows the \(l\)-adic approach of the seminal paper of \textit{R. Schoof} [Math. Comput. 44, 483--494 (1985; Zbl 0579.14025)] to compute the number of points of an elliptic curve and later generalized to others curves and varieties, see [\textit{L. M. Adleman} and \textit{M.-D. Huang}, J. Symb. Comput. 32, No. 3, 171--189 (2001; Zbl 0986.11039)]: to compute the characteristic polynomial of the Frobenius endomorphism \(\pi\)\, one takes enough (small) primes \(l\)\, and their action on the \(l\)-torsion of \(\mathrm{Jac}(\mathcal{C})\) is computed; then one uses the Chinese Remainder Theorem. The present paper takes primes \(l\)\, such that the ideal \(l\mathbb{Z}[\eta]\)\, split as a product \(\mathfrak{p}_1\mathfrak{p}_2\mathfrak{p}_3\)\, of prime ideals. The main result is formulated as Theorem 1 in Section 1 and Section 2 gives an overview (``a bird-eye view'') of the proposed algorithm (Algorithm 1) and it calculates its complexity module some technical results, which are discussed in the following sections (Sections 3 to 6). \par Section 7 gives details of the application of the algorithm to the particular curve \(\mathcal{C}: y^2=x^7 -7x^5+14x^3-7x+42\),\, (curve member of a family of genus-3 hyperelliptic curves with real multiplication studied by \textit{W. Tautz} et al. [Can. J. Math. 43, No. 5, 1055--1064 (1991; Zbl 0793.14022)]), curve defined over the field \(\mathbb{F}_p,\, \, p= 2^{64}-59\). For the entire collection see [Zbl 1416.11009].