A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm

Abstract : We present an algorithm based on the birthday paradox, which is a low-memory parallel counterpart to the algorithm of Matsuo, Chao and Tsujii. This algorithm computes the group order of the Jacobian of a genus 2 curve over a finite field for which the characteristic polynomial of the Frobenius endomorphism is known modulo some integer. The main tool is a 2-dimensional pseudo-random walk that allows to heuristically choose random elements in a 2-dimensional space. We analyze the expected running time based on heuristics that we validate by computer experiments. Compared with the original algorithm by Matsuo, Chao and Tsujii, we lose a factor of about 3 in running time, but the memory requirement drops from several GB to almost nothing. Our method is general and can be applied in other contexts to transform a baby-step giant-step approach into a low memory algorithm.
Type de document :
Communication dans un congrès
Duncan Buell. ANTS-VI, 2004, Burlington, United States. Springer Verlag, 3076, pp.208-222, 2004, LNCS. 〈10.1007/978-3-540-24847-7_15〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00514089
Contributeur : Pierrick Gaudry <>
Soumis le : mercredi 1 septembre 2010 - 10:54:18
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : jeudi 2 décembre 2010 - 02:41:58

Fichier

LMPMCT.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierrick Gaudry, Eric Schost. A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm. Duncan Buell. ANTS-VI, 2004, Burlington, United States. Springer Verlag, 3076, pp.208-222, 2004, LNCS. 〈10.1007/978-3-540-24847-7_15〉. 〈inria-00514089〉

Partager

Métriques

Consultations de la notice

139

Téléchargements de fichiers

82