A 𝑝+1 method of factoring

Williams, H. C.

doi:10.1090/S0025-5718-1982-0658227-7

A method of factoring

Author: H. C. Williams
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let N have a prime divisor p such that 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 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.

[1] Richard P. Brent, The first occurrence of certain large prime gaps, Math. Comp. 35 (1980), no. 152, 1435–1436. MR 583521, https://doi.org/10.1090/S0025-5718-1980-0583521-6
[2] 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.)
[3] Richard K. Guy, How to factor a number, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1975) Utilitas Math. Publ., Winnipeg, Man., 1976, pp. 49–89. Congressus Numerantium, No. XVI. MR 0404120
[4] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
[5] D. H. Lehmer, An extended theory of Lucas’ functions, Ann. of Math. (2) 31 (1930), no. 3, 419–448. MR 1502953, https://doi.org/10.2307/1968235
[6] D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assoc. Amer. (distributed by Prentice-Hall, Englewood Cliffs, N.J.), 1969, pp. 117–151. MR 0246815
[7] Michael A. Morrison and John Brillhart, The factorization of 𝐹₇, Bull. Amer. Math. Soc. 77 (1971), 264. MR 268113, https://doi.org/10.1090/S0002-9904-1971-12711-8
[8] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, https://doi.org/10.1017/s0305004100049252
[9] 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, https://doi.org/10.1090/S0025-5718-1976-0414473-6