The algebraic polynomial factorizations are well known "in theory." If n is odd, substituting

for x in the cyclotomic polynomial

yields a polynomial that splits into two Aurifeuillian polynomial factors A(x) and A(-x). (For n = 4, substituting 2x

^{2} for x in x

^{2} + 1 does the trick.)

For example, substituting -3*x^2 for x in x^2 + x + 1 gives 9*x^4 - 3*x^2 + 1, which factors as (3*x^2 + 3*x + 1)*(3*x^2 - 3*x + 1).

If you use this algebraic factorization to compute the factors in a numerical instance with n of any size, you have to be able to evaluate at least one of the polynomials at the appropriate argument value. Previous approaches were based on, for example, computing the coefficients as efficiently as possible.

The formula in the "Chinese paper," however, is not based on finding or evaluating the algebraic polynomial factors. It uses instead the evaluation of expressions that look Gauss sums, and expresses the factors as gcd's. The result that the gcd's actually give the Aurifeuillian factors is what is proven in the paper.

Whether you understand

*why* the formula works (and I don't), it is

*much* easier to use than methods requiring evaluating the Aurifeuillian factor polynomials.

I note that the paper only applies directly to numerical Aurifeuillian factorizations of M^n + or - 1; however, as is well known, this factorization "cuts across" the usual cyclotomic factors.