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 irreducibles, 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.”

The improvement relies heavily on a connection between skew polynomial rings and Azumaya algebras, and a little-known paper [2]. There is also substantial attention paid to the base algorithms for multiplying and gcd computation of skew polynomials. There are asymptotically fast ones depending on fast multiplication, and, probably more relevant in practice, a Karatsuba-like one. The detailed complexity results are too complicated to reproduce here, but the headline exponent of d in their complexity result is 3/2+o(1) versus the 4 in [1].

The code is available, and the authors state that there is an online demonstration via SageMath notebooks, though I was unable to get that to work.