A 𝑝+1 method of factoring

Williams, H. C.

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

A $p+1$ method of factoring
HTML articles powered by AMS MathViewer

by H. C. Williams PDF

Math. Comp. 39 (1982), 225-234 Request permission

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

Richard P. Brent, The first occurrence of certain large prime gaps, Math. Comp. 35 (1980), no. 152, 1435–1436. MR 583521, DOI 10.1090/S0025-5718-1980-0583521-6

Factorizations of

Up to High Powers

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