Tables of Fibonacci and Lucas factorizations
Authors:
John Brillhart, Peter L. Montgomery and Robert D. Silverman
Journal:
Math. Comp. 50 (1988), 251260, S1
MSC:
Primary 1104; Secondary 11B39
MathSciNet review:
917832
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We list the known prime factors of the Fibonacci numbers for and Lucas numbers for . We discuss the various methods used to obtain these factorizations, and primality tests, and give some history of the subject.
 [1]
J. Brillhart, "Fibonacci century mark reached," Fibonacci Quart., v. 1, 1963, p. 45.
 [2]
J. Brillhart, "Some miscellaneous factorizations," Math. Comp., v. 17, 1963, pp. 447450.
 [3]
John
Brillhart, D.
H. Lehmer, and J.
L. Selfridge, New primality criteria and
factorizations of 2^{𝑚}±1, Math.
Comp. 29 (1975),
620–647. MR 0384673
(52 #5546), http://dx.doi.org/10.1090/S00255718197503846731
 [4]
J. Brillhart, "UMT of for and for ," Math. Comp., submitted to unpublished tables.
 [5]
John
Brillhart, D.
H. Lehmer, J.
L. Selfridge, Bryant
Tuckerman, and S.
S. Wagstaff Jr., Factorizations of 𝑏ⁿ±1,
Contemporary Mathematics, vol. 22, American Mathematical Society,
Providence, R.I., 1983. 𝑏=2,3,5,6,7,10,11,12 up to high powers. MR 715603
(84k:10005)
 [6]
H.
Cohen and H.
W. Lenstra Jr., Primality testing and Jacobi
sums, Math. Comp. 42
(1984), no. 165, 297–330. MR 726006
(86g:11078), http://dx.doi.org/10.1090/S0025571819840726006X
 [7]
J. A. Davis & D. B. Holdridge, Most Wanted Factorizations Using the Quadratic Sieve, Sandia Report SAND841658, 1984.
 [8]
Joseph
L. Gerver, Factoring large numbers with a
quadratic sieve, Math. Comp.
41 (1983), no. 163, 287–294. MR 701639
(85c:11122), http://dx.doi.org/10.1090/S00255718198307016394
 [9]
D. Jarden, Recurring Sequences, 3rd ed., Riveon Lematematika, Jerusalem, 1973.
 [10]
D. H. Lehmer, "An announcement concerning the Delay Line Sieve DLS 127," Math. Comp., v. 20, 1966, pp. 645646.
 [11]
H. W. Lenstra, Jr., "Factoring integers with elliptic curves," Ann. of Math. (To appear.)
 [12]
Peter
L. Montgomery, Modular multiplication without trial
division, Math. Comp. 44
(1985), no. 170, 519–521. MR 777282
(86e:11121), http://dx.doi.org/10.1090/S0025571819850777282X
 [13]
Peter
L. Montgomery, Speeding the Pollard and elliptic
curve methods of factorization, Math. Comp.
48 (1987), no. 177, 243–264. MR 866113
(88e:11130), http://dx.doi.org/10.1090/S00255718198708661137
 [14]
Michael
A. Morrison and John
Brillhart, A method of factoring and the
factorization of 𝐹₇, Math.
Comp. 29 (1975),
183–205. Collection of articles dedicated to Derrick Henry Lehmer on
the occasion of his seventieth birthday. MR 0371800
(51 #8017), http://dx.doi.org/10.1090/S00255718197503718005
 [15]
T. Naur, Integer Factorization, DAIMI PB144, Computer Science Department, Aarhus University, Denmark, 1982.
 [16]
Thorkil
Naur, New integer factorizations,
Math. Comp. 41 (1983), no. 164, 687–695. MR 717713
(85c:11123), http://dx.doi.org/10.1090/S00255718198307177132
 [17]
Robert
D. Silverman, The multiple polynomial quadratic
sieve, Math. Comp. 48
(1987), no. 177, 329–339. MR 866119
(88c:11079), http://dx.doi.org/10.1090/S00255718198708661198
 [18]
Robert D. Silverman, "Parallel implementation of the quadratic sieve," The Journal of Supercomputing, v. 1, 1987, no. 3.
 [19]
H.
C. Williams, A 𝑝+1 method of
factoring, Math. Comp. 39
(1982), no. 159, 225–234. MR 658227
(83h:10016), http://dx.doi.org/10.1090/S00255718198206582277
 [20]
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
 [21]
H. C. Williams, private communication.
 [1]
 J. Brillhart, "Fibonacci century mark reached," Fibonacci Quart., v. 1, 1963, p. 45.
 [2]
 J. Brillhart, "Some miscellaneous factorizations," Math. Comp., v. 17, 1963, pp. 447450.
 [3]
 J. Brillhart, D. H. Lehmer & J. L. Selfridge, "New primality criteria and factorizations of ," Math. Comp., v. 29, 1975, pp. 620647. MR 0384673 (52:5546)
 [4]
 J. Brillhart, "UMT of for and for ," Math. Comp., submitted to unpublished tables.
 [5]
 J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman & S. S. Wagstaff, Jr., Factorizations of , Up to High Powers, Contemp. Math., vol. 22, Amer. Math. Soc., Providence, R.I., 1983. MR 715603 (84k:10005)
 [6]
 H. Cohen & H. W. Lenstra, Jr., "Primality testing and Jacobi sums," Math. Comp., v. 42, 1984, pp. 297330. MR 726006 (86g:11078)
 [7]
 J. A. Davis & D. B. Holdridge, Most Wanted Factorizations Using the Quadratic Sieve, Sandia Report SAND841658, 1984.
 [8]
 J. L. Gerver, "Factoring large numbers with a quadratic sieve," Math. Comp., v. 41, 1983, pp. 287294. MR 701639 (85c:11122)
 [9]
 D. Jarden, Recurring Sequences, 3rd ed., Riveon Lematematika, Jerusalem, 1973.
 [10]
 D. H. Lehmer, "An announcement concerning the Delay Line Sieve DLS 127," Math. Comp., v. 20, 1966, pp. 645646.
 [11]
 H. W. Lenstra, Jr., "Factoring integers with elliptic curves," Ann. of Math. (To appear.)
 [12]
 Peter L. Montgomery, "Modular multiplication without trial division," Math. Comp., v. 44, 1985, pp. 519521. MR 777282 (86e:11121)
 [13]
 Peter L. Montgomery, "Speeding the Pollard and elliptic curve methods of factorization," Math. Comp., v. 48, 1987, pp. 243264. MR 866113 (88e:11130)
 [14]
 M. A. Morrison & J. Brillhart, "A method of factoring and the factorization of ," Math. Comp., v. 29, 1975, pp. 183205. MR 0371800 (51:8017)
 [15]
 T. Naur, Integer Factorization, DAIMI PB144, Computer Science Department, Aarhus University, Denmark, 1982.
 [16]
 T. Naur, "New integer factorizations," Math. Comp., v. 41, 1983, pp. 687695. MR 717713 (85c:11123)
 [17]
 Robert D. Silverman, "The multiple polynomial quadratic sieve," Math. Comp., v. 48, 1987, pp. 329339. MR 866119 (88c:11079)
 [18]
 Robert D. Silverman, "Parallel implementation of the quadratic sieve," The Journal of Supercomputing, v. 1, 1987, no. 3.
 [19]
 H. C. Williams, " A method of factoring," Math. Comp., v. 39, 1982, pp. 225234. MR 658227 (83h:10016)
 [20]
 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)
 [21]
 H. C. Williams, private communication.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
1104,
11B39
Retrieve articles in all journals
with MSC:
1104,
11B39
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198809178326
PII:
S 00255718(1988)09178326
Keywords:
Factor tables,
Fibonacci,
Lucas,
factorizations
Article copyright:
© Copyright 1988 American Mathematical Society
