Paper 2021/792

Pseudo-Random Walk on Ideals: Practical Speed-Up in Relation Collection for Class Group Computation

Madhurima Mukhopadhyay and Palash Sarkar

Abstract

We introduce a technique to obtain practical speed up for relation collection in class group computations. The idea is to perform a pseudo-random walk over the ideals. The ideals visited by the walk are used in the manner exactly as in the previous algorithm due to Gélin (2018). Under the heuristic assumption that the ideals visited by the walk behave as the ideals randomly generated in Gélin’s algorithm, the asymptotic complexity of the new algorithm remains the same as that of Gélin’s algorithm. The main advantage of the new method over Gélin’s method is that the pseudo-random walk requires a single ideal multiplication to generate the next ideal in the walk, whereas Gélin’s algorithm requires a number of ideal multiplications to generate each ideal to be tested. We have made Magma implementations of both the new algorithm and Gélin’s algorithm. Timing results confirm that there is indeed a substantial practical speed-up in relation collection by the new algorithm over Gélin’s algorithm.

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Keywords
class grouppseudo-random walk
Contact author(s)
mukhopadhyaymadhurima @ gmail com
madhurima_r @ isical ac in
palash @ isical ac in
History
2021-10-15: revised
2021-06-14: received
See all versions
Short URL
https://ia.cr/2021/792
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/792,
      author = {Madhurima Mukhopadhyay and Palash Sarkar},
      title = {Pseudo-Random Walk on Ideals: Practical Speed-Up in Relation Collection for Class Group Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/792},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/792}},
      url = {https://eprint.iacr.org/2021/792}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.