An efficient implementation of an exponential point-counting algorithm on Jacobians of genus 2 hyperelliptic curves
- Pages
- 42-48
Abstract
Computing the order of Jacobian of a hyperelliptic curve is a common number-theoretical problem that has lots of applications in modern cryptography. Namely, Jacobians are applicable to constructions of DLP-based cryptosystems, 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 present an overview of approaches to accelerate Gaudry-Schost point counting algorithm that is the fastest known algorithm for computing the order of Jacobians of hyperelliptic curves of genus 2. This algorithm consists of two stages: 1) computing the number of points (equivalently, the characteristic polynomial 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. However, 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 exponential part of Gaudry-Schost’s point counting algorithm. We evaluate the efficiency of our multithreaded implementation.