Improved Stage 2 to P ± 1 Factoring Algorithms

DOI10.1007/978-3-540-79456-1_12zbMath1230.11149OpenAlexW1579824919MaRDI QIDQ5387598

Alexander Kruppa, Peter L. Montgomery

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79456-1_12

zbMATH Keywords

convolutiondiscrete Fourier transformInteger factorizationreciprocal polynomialsnumber theoretic transformmultipoint polynomial evaluationPollard's \(p-1\) factoring methodWilliams' \(p+1\) factoring method

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Factorization (11Y05)

Cites Work

• Unnamed Item
• Unnamed Item
• Fast polynomial multiplication and convolutions related to the discrete cosine transform
• Modular Multiplication Without Trial Division
• Modular exponentiation via the explicit Chinese remainder theorem
• An FFT Extension to the P - 1 Factoring Algorithm
• Speeding the Pollard and Elliptic Curve Methods of Factorization
• A p + 1 Method of Factoring
• Discrete Weighted Transforms and Large-Integer Arithmetic
• Algorithmic Number Theory

This page was built for publication: Improved Stage 2 to P ± 1 Factoring Algorithms