Tables of Fibonacci and Lucas factorizations

Authors:
John Brillhart, Peter L. Montgomery and Robert D. Silverman

Journal:
Math. Comp. **50** (1988), 251-260, S1

MSC:
Primary 11-04; Secondary 11B39

DOI:
https://doi.org/10.1090/S0025-5718-1988-0917832-6

MathSciNet review:
917832

Full-text PDF

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. 447-450.**[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**, https://doi.org/10.1090/S0025-5718-1975-0384673-1**[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****[6]**H. Cohen and H. W. Lenstra Jr.,*Primality testing and Jacobi sums*, Math. Comp.**42**(1984), no. 165, 297–330. MR**726006**, https://doi.org/10.1090/S0025-5718-1984-0726006-X**[7]**J. A. Davis & D. B. Holdridge,*Most Wanted Factorizations Using the Quadratic Sieve*, Sandia Report SAND84-1658, 1984.**[8]**Joseph L. Gerver,*Factoring large numbers with a quadratic sieve*, Math. Comp.**41**(1983), no. 163, 287–294. MR**701639**, https://doi.org/10.1090/S0025-5718-1983-0701639-4**[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. 645-646.**[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**, https://doi.org/10.1090/S0025-5718-1985-0777282-X**[13]**Peter L. Montgomery,*Speeding the Pollard and elliptic curve methods of factorization*, Math. Comp.**48**(1987), no. 177, 243–264. MR**866113**, https://doi.org/10.1090/S0025-5718-1987-0866113-7**[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**, https://doi.org/10.1090/S0025-5718-1975-0371800-5**[15]**T. Naur,*Integer Factorization*, DAIMI PB-144, Computer Science Department, Aarhus University, Denmark, 1982.**[16]**Thorkil Naur,*New integer factorizations*, Math. Comp.**41**(1983), no. 164, 687–695. MR**717713**, https://doi.org/10.1090/S0025-5718-1983-0717713-2**[17]**Robert D. Silverman,*The multiple polynomial quadratic sieve*, Math. Comp.**48**(1987), no. 177, 329–339. MR**866119**, https://doi.org/10.1090/S0025-5718-1987-0866119-8**[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**, https://doi.org/10.1090/S0025-5718-1982-0658227-7**[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**, https://doi.org/10.1090/S0025-5718-1976-0414473-6**[21]**H. C. Williams, private communication.

Retrieve articles in *Mathematics of Computation*
with MSC:
11-04,
11B39

Retrieve articles in all journals with MSC: 11-04, 11B39

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1988-0917832-6

Keywords:
Factor tables,
Fibonacci,
Lucas,
factorizations

Article copyright:
© Copyright 1988
American Mathematical Society