Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00514089
Contributor : Pierrick Gaudry <>
Submitted on : Wednesday, September 1, 2010 - 10:54:18 AM
Last modification on : Thursday, March 5, 2020 - 6:21:50 PM
Long-term archiving on: : Thursday, December 2, 2010 - 2:41:58 AM

File

LMPMCT.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Pierrick Gaudry, Eric Schost. A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm. ANTS-VI, 2004, Burlington, United States. pp.208-222, ⟨10.1007/978-3-540-24847-7_15⟩. ⟨inria-00514089⟩

Share

Metrics

Record views

242

Files downloads

345