Addition of divisors on hyperelliptic curves via interpolation polynomials (Q2190679)

Given an algebraic curve \( C \) of genus \( g \), it follows from the Riemann-Roch theorem that every non-special divisor on \( C \) of the form \(D-(\deg D)\infty\) is equivalent to \(\tilde{D}-g\infty\), where \(\tilde{D}=\sum_{k=1}^{g}P_k\), \(P_k\in C\), is \textit{a reduced divisor}. The first result in finding a reduced divisor was given in [\textit{D.G. Cantor}, Math. Comp. 48, 95--101 (1987; Zbl 0613.14022)]. Cantor's algorithm was inspired by reduction of quadratic forms. For low genera (\( g = 2, 3 \)) many authors worked on giving more explicit solutions to the reduction problem due to potential application in cryptography, see [\textit{P. Gaudry}, J. Math. Cryptol. 1, 243--265 (2007; Zbl 1145.11048)] and [\textit{A. V. Sutherland}, ``Fast Jacobian arithmetic for hyperelliptic curves of genus 3'', Preprint, \url{arXiv:1607.08602}] and the literature cited there. The authors propose an effective algorithm that reduce an arbitrary degree non-special divisor on a hyperelliptic curve \(C\) to the equivalent one of degree \(g\). The advantage of the algorithm is that it involves only arithmetic operations on polynomials. The reduced divisor is obtained in the form of solution to the Jacobi inversion problem. Explicit formulas defining the reduced divisor \( \tilde{D} \) are found, with the help of interpolation polynomials, for an initial divisor of the form \( D_{g+1}=\sum_{k=1}^{g+1}P_k \), \(D_{g+2}=\sum_{k=1}^{g+2}P_k \), \( D_{g+1}=2P_1+\sum_{k=2}^{g}P_k \) with all \( P_k\in C \) distinct, and for \(D_{g+1}=(g + 1)P \) with \( P\in C \). The polynomials defining \( \tilde{D} \) are expressed in terms of the points \( P_k \), their coefficients computed directly. An iterative reduction algorithm is given for \( D_{g+m}=\sum_{k=1}^{g+m}P_k\), \(m>2 \), with all \( P_k\in C \) distinct. It is proposed a cryptography application of the algorithm that is extended to divisors of arbitrary degrees comparing with the known ones in the theory of hyperelliptic functions. The authors also solve an addition problem: given two non-special divisors \(D_1 \) and \( D_2 \) of degrees \( g + m_1 \) and \( g + m_2 \), \( m_1, m_2 > 0 \), find a reduced divisor \( \tilde{D} \) of degree \( g \) such that \( D_1+D_2-(2g+m_1+m_2)\infty\sim\tilde{D}-g\infty\). The addition algorithm is also applicable to special divisors of degree \( m < g \) provided that their sum is a non-special divisor of degree greater than \( g \).