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.**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**0268113**, 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**0354514****[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**0414473**, 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