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

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.*, v. 35, 1980, pp. 1435-1436. MR**583521 (81g:10002)****[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,"*Congressus Numerantium*XVI, Proc. Fifth Manitoba Conf. on Numerical Math., Winnipeg, 1976, pp. 49-89. MR**0404120 (53:7924)****[4]**Donald E. Knuth,*The Art of Computer Programming*, Vol. II,*Seminumerical Algorithms*, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR**633878 (83i:68003)****[5]**D. H. Lehmer, "An extended theory of Lucas' functions,"*Ann. of Math.*(2), v. 31, 1930, pp. 419-448. MR**1502953****[6]**D. H. Lehmer, "Computer technology applied to the theory of numbers," in*Studies in Number Theory*(W. J. LeVeque, ed.), Math. Assoc. Amer. Studies in Math., vol. 6, 1969, pp. 117-151. MR**0246815 (40:84)****[7]**Michael A. Morrison & John Brillhart, "The factorization of ,"*Bull. Amer. Math. Soc.*, v. 77, 1971, p. 264. MR**0268113 (42:3012)****[8]**J. M. Pollard, "Theorems on factorization and primality testing,"*Proc. Cambridge Philos. Soc.*, v. 76, 1974, pp. 521-528. MR**0354514 (50:6992)****[9]**H. C. Williams & J. S. Judd, "Some algorithms for prime testing using generalized Lehmer functions,"*Math. Comp.*, v. 30, 1976, pp. 867-886. MR**0414473 (54:2574)**

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