Does CRT work for Fq[x]?

24 Views Asked by At

Given two linear polynomials $b_1(x),b_2(x)\in\Bbb F_q[x]$ say I know a third linear polynomial $b(x)$ has $u(x)\equiv b(x)\bmod b_1(x)$ and $v(x)\equiv b(x)\bmod b_2(x)$.

I think coprimality of $b_1(x)$ and $b_2(x)$ is necessary.

Can I reconstruct $b(x)$ uniquely?

What if $b(x)$ is quadratic?

How can one tell from $u(x)$ and $v(x)$ that $b(x)$ is degree $1$ or degree $2$?

1

There are 1 best solutions below

1
On

The Chinese remainder theorem is valid in any P.I.D. Its abstract version is this:

If $b_1$ and $b_2$ are two coprime elements in a P.I.D. $R$ then the canonical map \begin{align} R/b_1b_2R&\simeq R/b1R\times R/b2R\\ x\bmod b_1b_2&\mapsto(x\bmod b_1, x\bmod b_2) \end{align} is an isomorphism. Further, if $\lambda_1b_1+\lambda_2b_2=1$ is a Bézout's relation between $b_1$ and $b_2$, the inverse isomorphism is given by $$(x_1\bmod b_1, x_2\bmod b_2)\mapsto x_2\lambda_1b_1+x_1\lambda_2b_2\bmod b_1b_2.$$

So all you have to do is finding a Bézout's relation between the moduli. Except in simple cases, this is done through the extended Euclidean algorithm.