Computational Methods in Discrete Mathematics

Implementation of point-counting algorithms on genus $2$ hyperelliptic curves based on the birthday paradox

N. S. Kolesnikov

Immanuel Kant Baltic Federal University, Kaliningrad, Russia

Abstract: Our main contribution is an efficient implementation of the Gaudry — Schost and Galbraith — Ruprai point-counting algorithms on Jacobians of hyperelliptic curves. Both of them are low memory variants of Matsuo — Chao — Tsujii (MCT) Baby-Step Giant-Step-like algorithm. We present an optimal memory restriction (a time-memory tradeoff) that minimizes the runtime of the algorithms. This tradeoff allows us to get closer in practical computations to theoretical bounds of expected runtime at $2.45\sqrt{N}$ and $2.38\sqrt{N}$ for the Gaudry — Schost and Galbraith — Ruprai algorithms, respectively. Here $N$ is the size of the $2$-dimensional searching space, which is as large as the Jacobian group order, divided by small modulus $m$, precomputed by using other techniques. Our implementation profits from the multithreaded regime and we provide some performance statistics of operation on different size inputs. This is the first open-source parallel implementation of $2$-dimensional Galbraith — Ruprai algorithm.

Keywords: hyperelliptic curve, Jacobian, point-counting, birthday paradox.

UDC: 512.772

Language: English

DOI: 10.17223/20710410/55/9

Bibliographic databases:

•