Aurifeuillian factorization

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.