2023/05/29 by Stephen M. Watt, Watt, Stephen M.
Computer Science · #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.2305.17877
openalex publication_date 2023/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is shown how to compute quotients efficiently in non-commutative univariate polynomial rings. This extends earlier work where efficient generic quotients were studied with a primary focus on commutative domains. Fast algorithms are given for left and right quotients of polynomials where the variable commutes with coefficients. These algorithms are based on the concept of the ``whole shifted inverse'', which is a specialized quotient where the dividend is a power of the polynomial variable. It is also shown that when the variable does not commute with coefficients, that is for skew polynomials, left and right whole shifted inverses are defined and may be used to compute right and left quotients. In this case their computation is not asymptotically fast, but once obtained, they may be used to compute multiple quotients, each with one multiplication. Examples are shown of polynomials with matrix coefficients, differential operators and difference operators. In addition, a proof-of-concept generic Maple implementations is given.