A $p+1$ method of factoring
HTML articles powered by AMS MathViewer
- by H. C. Williams PDF
- Math. Comp. 39 (1982), 225-234 Request permission
Abstract:
Let N have a prime divisor p such that $p + 1$ has only small prime divisors. A method is described which will allow for the determination of p, given N. This method is analogous to the $p - 1$ method of factoring which was described in 1974 by Pollard. The results of testing this method on a large number of composite numbers are also presented.References
- 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 John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman & S. S. Wagstaff, Jr., Factorizations of ${b^n} \pm 1,b = 2,3,5,7,10,11,12$ Up to High Powers. (To appear.)
- Richard K. Guy, How to factor a number, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1975) Congressus Numerantium, No. XVI, Utilitas Math. Publ., Winnipeg, Man., 1976, pp. 49–89. MR 0404120
- 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
- D. H. Lehmer, An extended theory of Lucas’ functions, Ann. of Math. (2) 31 (1930), no. 3, 419–448. MR 1502953, DOI 10.2307/1968235
- D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assoc. America, Buffalo, N.Y.; distributed by Prentice-Hall, Englewood Cliffs, N.J., 1969, pp. 117–151. MR 0246815
- Michael A. Morrison and John Brillhart, The factorization of $F_{7}$, Bull. Amer. Math. Soc. 77 (1971), 264. MR 268113, DOI 10.1090/S0002-9904-1971-12711-8
- J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252
- H. C. Williams and J. S. Judd, Some algorithms for prime testing using generalized Lehmer functions, Math. Comp. 30 (1976), no. 136, 867–886. MR 414473, DOI 10.1090/S0025-5718-1976-0414473-6
Additional Information
- © Copyright 1982 American Mathematical Society
- Journal: Math. Comp. 39 (1982), 225-234
- MSC: Primary 10A25; Secondary 10-04
- DOI: https://doi.org/10.1090/S0025-5718-1982-0658227-7
- MathSciNet review: 658227