FFT extension for algebraic-group factorization algorithms

Richard P. Brent (1) , Alexander Kruppa (2) , Paul Zimmermann (3)

1 MSI - Mathematical Sciences Institute
2 TUM - Technische Universität Munchen - Technical University Munich - Université Technique de Munich
3 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms

It is well known that the second stage of factoring methods that exploit smoothness of group orders can be implemented efficiently using the fast Fourier transform (FFT). For Pollard's p−1 method [17] this originated with the Mont-gomery and Silverman paper [16], and for the elliptic curve factoring method [12] it was the subject of Peter Montgomery's PhD dissertation [14]. Along with Peter's most recent work on this subject [15], these developments are presented in this chapter.

Domaines: Algorithme et structure de données [cs.DS]

Richard P. Brent, Alexander Kruppa, Paul Zimmermann. FFT extension for algebraic-group factorization algorithms. Joppe W. Bos; Arjen K. Lenstra. Topics in Computational Number Theory Inspired by Peter L. Montgomery, Cambridge University Press, pp.189-205, 2017, 978-1-107-10935-3. ⟨hal-01630907⟩