Thread: Aurifeuillian Factorizations View Single Post
 2020-08-28, 14:34 #40 Dr Sardonicus     Feb 2017 Nowhere 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.