Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Aurifeuillian factorization

Authors: Andrew Granville and Peter Pleasants
Journal: Math. Comp. 75 (2006), 497-508
MSC (2000): Primary 11Y05; Secondary 11T22, 11Y40, 12Y05
Published electronically: June 16, 2005
MathSciNet review: 2176412
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The Cunningham project seeks to factor numbers of the form $b^{n}\pm 1$ with $b=2,3,\dots $ small. One of the most useful techniques is Aurifeuillian Factorization whereby such a number is partially factored by replacing $b^{n}$ by a polynomial in such a way that polynomial factorization is possible. For example, by substituting $y=2^{k}$ into the polynomial factorization $(2y^{2})^{2}+1=(2y^{2}-2y+1)(2y^{2}+2y+1)$ we can partially factor $2^{4k+2}+1$. In 1962 Schinzel gave a list of such identities that have proved useful in the Cunningham project; we believe that Schinzel identified all numbers that can be factored by such identities and we prove this if one accepts our definition of what ``such an identity'' is. We then develop our theme to similarly factor $f(b^{n})$ for any given polynomial $f$, using deep results of Faltings from algebraic geometry and Fried from the classification of finite simple groups.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y05, 11T22, 11Y40, 12Y05

Retrieve articles in all journals with MSC (2000): 11Y05, 11T22, 11Y40, 12Y05

Additional Information

Andrew Granville
Affiliation: Département de mathématiques et de statistique, Université de Montréal, CP 6128 succ. Centre-Ville, Montréal, Quebec H3C 3J7, Canada
Email: andrew@DMS.UMontreal.CA

Peter Pleasants
Affiliation: Department of Mathematics, University of Queensland, Queensland 4072, Australia

Received by editor(s): November 28, 2001
Received by editor(s) in revised form: June 1, 2004
Published electronically: June 16, 2005
Additional Notes: Le premier auteur est partiellement soutenu par une bourse du Conseil de recherches en sciences naturelles et en génie du Canada and was supported, in part, by the National Science Foundation when this project began.
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society