7
$\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
    $\begingroup$ It should be straightforward to do this two at a time, using PolynomialExtendedGCD as the primary tool. $\endgroup$ – Daniel Lichtblau Sep 18 '13 at 17:04
  • 1
    $\begingroup$ @DanielLichtblau Thank you for your hint. Following it I succeeded in defining the function PolynomialCRT. $\endgroup$ – Julián Aguirre Sep 19 '13 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$ – Daniel Lichtblau Sep 19 '13 at 18:53
9
$\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$
  • 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$ – Daniel Lichtblau Sep 20 '13 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 '16 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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