View Single Post
Old 2020-08-28, 14:34   #40
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

67348 Posts

The algebraic polynomial factorizations are well known "in theory." If n is odd, substituting (-1)^{\frac{n-1}{2}}nx^{2} for x in the cyclotomic polynomial \Phi_{n}(x) yields a polynomial that splits into two Aurifeuillian polynomial factors A(x) and A(-x). (For n = 4, substituting 2x2 for x in x2 + 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.
Dr Sardonicus is offline   Reply With Quote