9
$\begingroup$

I would like an implementation of the Chinese Remainder Theorem for polynomials in $\mathbb{Z}[x]$, that is, a function

PolynomialCRT[{f_1,...,f_n},{m_1,...,m_n},x]

thet returns the polynomial $f\in\mathbb{Z}[x]$ of smallest degree such that $$ f(x)\equiv f_i(x)\mod m_i(x), $$ where $f_i,m_i\in\mathbb{Z}[x]$ and the $m_i$ are pairwise coprime.

Any ideas?

Thanks in advance.

$\endgroup$
3
  • 3
    $\begingroup$ It should be straightforward to do this two at a time, using PolynomialExtendedGCD as the primary tool. $\endgroup$ Sep 18, 2013 at 17:04
  • 1
    $\begingroup$ @DanielLichtblau Thank you for your hint. Following it I succeeded in defining the function PolynomialCRT. $\endgroup$ Sep 19, 2013 at 16:25
  • 2
    $\begingroup$ You can post it here as a separate response. That way the Q has an A, and it is available should others in future make similar queries. That is to say, in a circumstance like this, it is not frowned upon if one answers one's own question. $\endgroup$ Sep 19, 2013 at 18:53

1 Answer 1

11
$\begingroup$

Following Daniel's comment, I post my solution:

PolynomialCRT[pol_List, mod_List, x_] := Module[{m, q, l},
  l = Length[pol];
  m = Table[Times @@ Drop[mod, {i}], {i, l}];
  q = Table[PolynomialExtendedGCD[m[[i]], mod[[i]], x][[2, 1]], {i, l}];
  Simplify[(q pol).m]
  ]

There is no error checking code (for instance, pol and mod have the same length).

$\endgroup$
2
  • 1
    $\begingroup$ Nice and short (and an upvote of course). One comment: if total degree is high, it could be faster to do it in pairs, then combining paired results in pairs, etc. That would tend to keep the degrees of the two moduli products balanced. We did this once upon a time in integer CRA code and it made a notable difference in terms of speed. $\endgroup$ Sep 20, 2013 at 14:38
  • 1
    $\begingroup$ +1. Sometimes the resulting polynomial is of degree more than necessary, so the last line should be changed to PolynomialRemainder[Simplify[(q pol).m], PolynomialLCM @@ mod, x]. Will Table[Times@@... line slower than procedural approach? $\endgroup$
    – user202729
    Sep 7, 2016 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.