## An FFT extension to the $P-1$ factoring algorithm

HTML articles powered by AMS MathViewer

- by Peter L. Montgomery and Robert D. Silverman PDF
- Math. Comp.
**54**(1990), 839-854 Request permission

## Abstract:

J. M. Pollard, in 1974, presented the $P - 1$ integer factoring algorithm. His paper couched the algorithm in theoretical terms based upon use of Fast Fourier Transform techniques, but he was unable to say whether the method could be made practical. We discuss the mathematical basis of the algorithm and show how it can work in practice. The practical implementation depends, for its success, upon the use of Residue Number Systems. We also present an open problem as to how the method could be made to work for the Elliptic Curve factoring algorithm.## References

- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,
*The design and analysis of computer algorithms*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR**0413592** - Allan Borodin and Ian Munro,
*The computational complexity of algebraic and numeric problems*, Elsevier Computer Science Library: Theory of Computation Series, No. 1, American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975. MR**0468309** - Richard P. Brent,
*The first occurrence of certain large prime gaps*, Math. Comp.**35**(1980), no. 152, 1435–1436. MR**583521**, DOI 10.1090/S0025-5718-1980-0583521-6
R. P. Brent, - John Brillhart, Peter L. Montgomery, and Robert D. Silverman,
*Tables of Fibonacci and Lucas factorizations*, Math. Comp.**50**(1988), no. 181, 251–260, S1–S15. MR**917832**, DOI 10.1090/S0025-5718-1988-0917832-6 - John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr.,
*Factorizations of $b^n \pm 1$*, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR**996414**, DOI 10.1090/conm/022
A. M. Despain, A. M. Peterson, O. S. Rothaus, and E. H. Wold, - Donald E. Knuth,
*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR**633878** - H. W. Lenstra Jr.,
*Factoring integers with elliptic curves*, Ann. of Math. (2)**126**(1987), no. 3, 649–673. MR**916721**, DOI 10.2307/1971363 - James H. McClellan and Charles M. Rader,
*Number theory in digital signal processing*, Prentice Hall Signal Processing Series, Prentice Hall, Inc., Englewood Cliffs, NJ, 1979. Including reprinted papers. MR**723867** - Peter L. Montgomery,
*Speeding the Pollard and elliptic curve methods of factorization*, Math. Comp.**48**(1987), no. 177, 243–264. MR**866113**, DOI 10.1090/S0025-5718-1987-0866113-7
A. Norton and A. J. Silberger, - Henri J. Nussbaumer,
*Fast Fourier transform and convolution algorithms*, Springer Series in Information Sciences, vol. 2, Springer-Verlag, Berlin-New York, 1981. MR**606376**, DOI 10.1007/978-3-662-00551-4 - J. M. Pollard,
*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**354514**, DOI 10.1017/s0305004100049252 - Joseph H. Silverman,
*The arithmetic of elliptic curves*, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR**817210**, DOI 10.1007/978-1-4757-1920-8 - H. C. Williams,
*A $p+1$ method of factoring*, Math. Comp.**39**(1982), no. 159, 225–234. MR**658227**, DOI 10.1090/S0025-5718-1982-0658227-7 - Jeff Young and Aaron Potler,
*First occurrence prime gaps*, Math. Comp.**52**(1989), no. 185, 221–224. MR**947470**, DOI 10.1090/S0025-5718-1989-0947470-1

*Some integer factorization algorithms using elliptic curves*, Research Report CMA-R32-85, The Center for Mathematical Analysis, The Australian National University, 1985.

*Fast Fourier transform processors using Gaussian residue arithmetic*, J. Parallel & Distributed Comp.

**2**(1985), 219-237.

*Parallelization and performance analysis of the Cooley-Tukey FFT algorithm for shared memory architectures*, IEEE Trans. Comp.

**C-36**(1987), 581-591.

## Additional Information

- © Copyright 1990 American Mathematical Society
- Journal: Math. Comp.
**54**(1990), 839-854 - MSC: Primary 11Y05
- DOI: https://doi.org/10.1090/S0025-5718-1990-1011444-3
- MathSciNet review: 1011444