Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A $ p+1$ 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 $ 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 [Enhancements On Off] (What's this?)

  • [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 $ {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," 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 $ {F_7}$," 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)

Similar Articles

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

American Mathematical Society