Physics, mathematics, and technology

2020 Issue №4

Back to the list Download the article

An efficient implementation of an exponential point-counting algorithm on Jacobians of genus 2 hyperelliptic curves



Computing the order of Jacobian of a hyperelliptic curve is a common number-theoretical problem that has lots of applications in modern cryptog­raphy. Namely, Jacobians are applicable to constructions of DLP-based cryp­tosystems, as well as constructions of verifiable delay functions (VDF’s), since they can be viewed as large groups of unknown order. In this article, we pre­sent an overview of approaches to accelerate Gaudry-Schost point counting algorithm that is the fastest known algorithm for computing the order of Jaco­bians of hyperelliptic curves of genus 2. This algorithm consists of two stages: 1) computing the number of points (equivalently, the characteristic polynomi­al of the curve) modulo some small primes and combining the result into a large module using CRT (polynomial-time part); 2) restoring the number of points utilizing modular data using algorithms based on birthday paradox (exponential-time part). Theoretically, the algorithm terminates after the first stage with  time-complexity, where  is a finite field modulus. How­ever, in practice we terminate the polynomial-time part (due to high memory consumption), and we proceed to the second, memory-efficient, exponential-time part. This article presents a multithreaded C++ implementation of expo­nential part of Gaudry-Schost’s point counting algorithm. We evaluate the ef­ficiency of our multithreaded implementation.