1

I know how to compute polynomial modular another polynomail in polynomial rings. But what is the fastest algorithm for computing polynomial modular two polynomails in polynomial ring?

For example: How to compute $f(x) \pmod{a(x),\ b(x)}$ in $R=\mathbb{Z}_n[x]$? In other word, how to efficiently find a polynomial $g(x)$ with minimal degree in $R$ such that $f(x)-g(x)$ is in the ideal $(a(x),\ b(x))$ of $R$.

Remark: $\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$.

J.R.
  • 121
  • 1
    Is n prime? $ $ – Math Gems Apr 13 '13 at 14:02
  • The notation $\mathbb{Z}_n$ is ambiguous. Is it the integers modulo $n$? Is it the $n$-adics? Or maybe even the integers localized at $n$? I have even seen it mean $\mathbb{Z}[\frac{1}{n}]$. –  Apr 13 '13 at 14:19
  • $\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$, with $n$ may be not a prime. – J.R. Apr 13 '13 at 14:23

1 Answers1

1

If $n$ is prime, the answer is easy enough, because then $\mathbb Z/(n)$ is a field, and $(a(x),b(x))=(\gcd(a,b))$. That is, your two-generator ideal is actually principal, generated by the greatest common divisor of the two polynomials. Even over $\mathbb Z/(6)$, however, the answer looks much less tractable. What if $a(x)=2x$ and $b(x)=3x^2$?

Lubin
  • 62,818