Geodesic
Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox
Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 120-128

Voir la notice de l'article provenant de la source Math-Net.Ru

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, point-counting, birthday paradox.
Mots-clés : Jacobian 
@article{PDM_2022_1_a8,
     author = {N. S. Kolesnikov},
     title = {Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {120--128},
     publisher = {mathdoc},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_1_a8/}
}
TY  - JOUR
AU  - N. S. Kolesnikov
TI  - Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 120
EP  - 128
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_1_a8/
LA  - en
ID  - PDM_2022_1_a8
ER  - 
%0 Journal Article
%A N. S. Kolesnikov
%T Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 120-128
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2022_1_a8/
%G en
%F PDM_2022_1_a8
N. S. Kolesnikov. Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox. Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 120-128. http://geodesic.mathdoc.fr/item/PDM_2022_1_a8/