Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
3  
It should be straightforward to do this two at a time, using PolynomialExtendedGCD as the primary tool. –  Daniel Lichtblau Sep 18 '13 at 17:04
1  
@DanielLichtblau Thank you for your hint. Following it I succeeded in defining the function PolynomialCRT. –  Julián Aguirre Sep 19 '13 at 16:25
1  
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. –  Daniel Lichtblau Sep 19 '13 at 18:53
add comment

1 Answer

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).

share|improve this answer
1  
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. –  Daniel Lichtblau Sep 20 '13 at 14:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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