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, Some integer factorization algorithms using elliptic curves, Research Report CMA-R32-85, The Center for Mathematical Analysis, The Australian National University, 1985.
- 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, Fast Fourier transform processors using Gaussian residue arithmetic, J. Parallel & Distributed Comp. 2 (1985), 219-237.
- 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, Parallelization and performance analysis of the Cooley-Tukey FFT algorithm for shared memory architectures, IEEE Trans. Comp. C-36 (1987), 581-591.
- 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
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