Let k be a finite field of characteristic p and size p^qr, and let σ be an automorphism of k of order r. The ring of skew polynomials k[X, σ] is defined as usual polynomial rings except that X • a = σ(a) • X, so that X^r • a = σ^r(a)• X^r = a • X^r, so multiplication by X^r is commutative. Typical examples for skew polynomials (not necessarily over finite fields) are differential and difference operators, while over finite fields they have applications in coding theory. Skew polynomials can be factored into irre-ducibles, but unlike commutative polynomials, the result is not necessarily unique. However, by a classical theorem of Ore, the factorizations are similar, where two skew polynomials P and Q are similar if there exist skew polynomials U and V such that UP = QV (and rgcd(P, V) = 1, lgcd(Q, U) = 1). "Similarity" turns out to be the correct generalization of "equal up to constant factors." Hence, the authors only require that their factorization algorithm returns one of the possible factorizations, just as we would expect "factor(30)" to return "2,3,5" rather than "2,3,5 or -2,5,-3 or ..." The authors summarize their paper well: "The strategy of our algorithm is roughly comparable to the one of [1]: in order to factor P, we find a multiple N of P lying in the center of k[X,σ], we factor N in the center (which is a commutative polynomial ring), and we recover a factorization of P from the factorization of N we have just computed."
展开▼
