A method of factoring
Author:
H. C. Williams
Journal:
Math. Comp. 39 (1982), 225234
MSC:
Primary 10A25; Secondary 1004
MathSciNet review:
658227
Fulltext 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
(81g:10002), http://dx.doi.org/10.1090/S00255718198005835216
 [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
(53 #7924)
 [4]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [5]
D.
H. Lehmer, An extended theory of Lucas’ functions, Ann.
of Math. (2) 31 (1930), no. 3, 419–448. MR
1502953, http://dx.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
PrenticeHall, Englewood Cliffs, N.J.), 1969, pp. 117–151. MR 0246815
(40 #84)
 [7]
Michael
A. Morrison and John
Brillhart, The factorization of
𝐹₇, Bull. Amer. Math. Soc.
77 (1971), 264. MR 0268113
(42 #3012), http://dx.doi.org/10.1090/S000299041971127118
 [8]
J.
M. Pollard, Theorems on factorization and primality testing,
Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 0354514
(50 #6992)
 [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
(54 #2574), http://dx.doi.org/10.1090/S00255718197604144736
 [1]
 Richard P. Brent, "The first occurrence of certain large prime gaps," Math. Comp., v. 35, 1980, pp. 14351436. 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. 4989. MR 0404120 (53:7924)
 [4]
 Donald E. Knuth, The Art of Computer Programming, Vol. II, Seminumerical Algorithms, 2nd ed., AddisonWesley, 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. 419448. 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. 117151. 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. 521528. 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. 867886. MR 0414473 (54:2574)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
10A25,
1004
Retrieve articles in all journals
with MSC:
10A25,
1004
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198206582277
PII:
S 00255718(1982)06582277
Article copyright:
© Copyright 1982
American Mathematical Society
