Index Calculus Algorithm for Non-Planar Curves

In this paper, we develop a variation of the index calculus algorithm using non-planar models of non-hyperelliptic curves of genus g. Using canonical model of degree 2g−2 in the projective space of dimension g−1, intersections with hyperplanes and following similar ideas to those of Diem (who used intersections with lines on planar models), we obtain an upper bound of [Formula presnted] for the computation of discrete logarithms for all non-hyperelliptic curves of genus g defined over the finite field Fq. This asymptotic cost is essentially the same as Diem s, but our algorithm offers several advantages over Diem s, including a constant speed-up. © 2023 Elsevier Inc.