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
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
Retrieve articles in Mathematics of Computation with MSC: 10A25, 10-04
Retrieve articles in all journals with MSC: 10A25, 10-04
Additional Information
DOI:
https://doi.org/10.1090/S0025-5718-1982-0658227-7
Article copyright:
© Copyright 1982
American Mathematical Society