An FFT extension to the 𝑃-1 factoring algorithm

Montgomery, Peter L.; Silverman, Robert D.

doi:10.1090/S0025-5718-1990-1011444-3

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

Some integer factorization algorithms using elliptic curves

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

Fast Fourier transform processors using Gaussian residue arithmetic

2

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

Parallelization and performance analysis of the Cooley-Tukey FFT algorithm for shared memory architectures

C-36

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