Addition of divisors on hyperelliptic curves via interpolation polynomials
type: Item
instance of: scholarly article
title: Addition of divisors on hyperelliptic curves via interpolation polynomials
zbMATH Open document ID: 1448.14025
DOI: 10.3842/SIGMA.2020.053
author: Yaacov Kopeliovich
author: J. N. Bernatska
published in: SIGMA. Symmetry, Integrability and Geometry: Methods and Applications
publication date: 2020-06-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/1912.13277
review text: 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 fu…
reviewed by: V. I. Zvonilov
Mathematics Subject Classification ID: 14H40
Mathematics Subject Classification ID: 14H45
Mathematics Subject Classification ID: 32Q30
Mathematics Subject Classification ID: 14G50
zbMATH DE Number: 7213585
zbMATH Keywords: reduced divisor
zbMATH Keywords: inverse divisor
zbMATH Keywords: non-special divisor
zbMATH Keywords: generalised Jacobi inversion problem
MaRDI profile type: MaRDI publication profile
arXiv ID: 1912.13277
cites work: Q4858736
cites work: Computing in the Jacobian of a Hyperelliptic Curve
cites work: Fast genus 2 arithmetic based on Theta functions
cites work: Fast Jacobian arithmetic for hyperelliptic curves of genus 3
cites work: Division polynomials and canonical local heights on hyperelliptic Jacobians
cites work: Canonical heights and division polynomials
cites work: Q3594470
cites work: Heat equations in a nonholomic frame
cites work: Q5301801
description: scientific article