|
Aurifeuillian factorizations and the period of the Bell numbers modulo a prime
Author(s):
Samuel
S.
Wagstaff Jr..
Journal:
Math. Comp.
65
(1996),
383-391.
MSC (1991):
Primary 11--04, 11B73;
Secondary 11Y05, 12--04, 12E10, 12Y05
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We show that the minimum period modulo  of the Bell exponential integers is  for all primes  and several larger  . Our proof of this result requires the prime factorization of these periods. For some primes  the factoring is aided by an algebraic formula called an Aurifeuillian factorization. We explain how the coefficients of the factors in these formulas may be computed.
References:
- 1
- H. W. Becker and D. H. Browne, Problem E461 and solution, Amer. Math. Monthly 48 (1941), 701--703.
- 2
- Richard P. Brent, On computing factors of cyclotomic polynomials, Math. Comp. 61 (1993), 131--149, MR 93m:11131.
- 3
- E. Cesaro, Sur une équation aux différences mêlées, Nouvelles Annales de Math. (3) 4 (1885), 36--40.
- 4
- A. J. C. Cunningham, Factorisation of
 and  , Messenger of Math. (2) 45 (1915), 49--75. - 5
- H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649--673, MR 89g:11125.
- 6
- Jack Levine and R. E. Dalton, Minimum periods, modulo
 , of first-order Bell exponential integers, Math. Comp. 16 (1962), 416--423, MR 26:6111. - 7
- E. Lucas, Théorèms d'arithmétique, Atti R. Accad. Sci. Torino 13 (1877--78), 271--284.
- 8
- ------, Sur la série récurrente de Fermat, Bull. Bibl. Storia Sc. Mat. e Fis. 11 (1878), 783--789.
- 9
- Carl Pomerance, The quadratic sieve factoring algorithm, Advances in Cryptology, Proceedings of EUROCRYPT 84 (T. Beth, N. Cot, and I. Ingemarsson, eds.), Springer-Verlag Lecture Notes in Comput. Sci., vol. 209, 1985, pp. (169--182), MR 86m:94003.
- 10
- Hans Riesel, Prime numbers and computer methods for factorization, Birkhäuser, Boston, 1985, MR 88k:11002.
- 11
- A. Schinzel, On the primitive prime factors of
 , Proc. Cambridge Philos. Soc. 58 (1962), 555--562, MR 26:1280. - 12
- J. Touchard, Propriétés arithmétiques de certains nombres recurrents, Ann. Soc. Sci. Bruxelles 53A (1933), 21--31.
- 13
- G. T. Williams, Numbers generated by the function
 , Amer. Math. Monthly 52 (1945), 323--327, MR 7:47e.
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(1991):
11--04, 11B73,
11Y05, 12--04, 12E10, 12Y05
Retrieve articles in all Journals with MSC
(1991):
11--04, 11B73,
11Y05, 12--04, 12E10, 12Y05
Additional Information:
Samuel
S.
Wagstaff
Jr.
Affiliation:
Department of Computer Sciences, Purdue University, West Lafayette, Indiana 47907
Email:
ssw@cs.purdue.edu
DOI:
10.1090/S0025-5718-96-00683-7
PII:
S 0025-5718(96)00683-7
Keywords:
Bell numbers,
period modulo $p$,
integer factorization,
Lucas' identities,
Aurifeuillian factorization
Received by editor(s):
August 24, 1993
Received by editor(s) in revised form:
January 26, 1995
Additional Notes:
Some of the computing reported in this work was performed on a MasPar computer at Purdue University which was supported in part by NSF Infrastructure Grant CDA-9015696.
Copyright of article:
Copyright
1996,
American Mathematical Society
|
Comments: webmaster@ams.org