Sieving in Function Fields (Q4947131)

The authors develop an efficient Jacobian class group algorithm from the hyperelliptic curve of genus \(g\), \(Y^2= \Delta(X)\) for \(\Delta\) monic of degree \(2g+1\) (with simple roots) over \(R= \mathbb{F}_q[X]\). From a factor base of primes \(p\in R\) and forms \(f_p= (a,b,c)\), \((\Delta= b^2- 4ac)\), representing \(p\) it is necessary to construct compositions \(\prod f_p^{x_p}\) representing principal forms and thereby find class relations by matrix reduction of vectors \(x_p\). Rather than factor random elements of \(R\) (principal ideals), they take equivalent forms to \((a,b,c)\) of the type \((ax^2+ bxy+ cy^2,*,*)\) with pairs \(x,y\) selected from a special sieve array [see \textit{J. L. Hafner} and \textit{K. S. McCurley}, J. Am. Math. Soc. 2, 837-850 (1989; Zbl 0702.11088)]. Evidence is presented for comparison of different sieving strategies [compare \textit{S. Paulus}, Algorithmic number theory, ANTS-II (Talence, 1996), Lect. Notes Comput. Sci. 1122, 243-257 (1996; Zbl 0917.11063)].