# Question about CRT

The question rephrased and compressed:

Let $F=F_2[a]$ be a finite extension field of the field of two elements $F_2$. We are given a polynomial $R(X)\in F[X]$, and pairwise coprime irreducible polynomials $m_1(X), m_2(X),\ldots, m_n(X)\in F[X]$. Let $M(X)=\prod_{i=1}^n m_i(X)$ be their product. Is it always possible to find polynomials $P(X)$, $Q_1(X)$ in the ring $F[X]$ such that they satisfy the polynomial congruence $$P(X)\equiv Q_1(X) R(X) \pmod{M(X)}$$ as well as the degree constraints $\deg(Q_1) \leq \dfrac{\deg (M)-1}{2}$, $\deg(P) \leq \dfrac{\deg (M)}{2}$?

If the answer is in the affirmative, then how can we efficiently compute the polynomials $b_i(X)$ satisfying the individual congruences $$P(X)^2\equiv b_i(X)R(X)^2 \pmod{m_i(X)}, \text{ for }\ i = 1,\ldots,n.$$

[The earlier formulation of the question follows.]

Given the following congruences, all polynomials are in $F[X]$ (where $F = \mathbb{F}_2/p(X)$) and $m_i(X)$ coprimes between them $$P(X)^2\equiv b_i(X)R(X)^2 \pmod{m_i(X)}, \text{ for } i = 1,\ldots,n.$$

Applying CRT, I get $$P(X)^2\equiv{Q(X)R(X)^2}\pmod{M(X)},$$

where $Q(X) = \sum_{i=1}^n{b_i(X)y_i(X)M_i(X)}\,$ with $M_i(X) = M(X)/m_i(X)$ and $y_i(X)$ is a multiplicative inverse of $M_i(X)$ module $m_i(X)$; $M(X) = \prod_{i=1}^{n}{m_i(X)}$

and resolving this quadratic equation I get:

$$P(X)\equiv Q_1(X)R(X) \pmod{M(X)}$$

For example:

For $K = \mathbb{F}_2, F = K/(X^4+X+1)$ and $a$ primitive element of $F$

Give:

$M = (X + 1) \cdot (X + a^2 + a + 1) \cdot (X + a^3 + a + 1) \cdot (X + a^3 + a^2)$

\eqalign{R &= a^2 X^3 + (a^3 + a) X^2 + (a^3 + 1) X\cr}

Applying CRT (with $b_i$ than variables) get

\eqalign{QR^2&=(a^3X^5 + a^3X^4 + a^3X^3 + a^{14}X^2 + a^{13}X + a^5) \cdot R^2 \cdot b_1 \cr & + (a^{12}X^5 + a^7X^4 + a^{12}X^3 + a^9X^2 + a^2X + a^8) \cdot R^2 \cdot b_2 \cr & + (a^5X^5 + a^{12}X^4 + a^5X^3 + a^{11}X^2 + a^9X + a^7) \cdot R^2 \cdot b_3 \cr & + (X^5 + a^6X^4 + X^3 + a^{13} X^2 + a X + a^4) \cdot R^2 \cdot b_4},

and obviusly I don't resolved this quadratic equation $$P^2\equiv QR^2 \pmod{M},$$, because the $b_i$'s are unknow values, but I will expect this expression :

$P\equiv{Q_1R}\pmod{M}$

My question: Let $M(X)$ and $R(X)$ is there any mode to choose $b_i$ and $P(X)$ where $\deg(Q_1) < \dfrac{\deg (M)-1}{2}$ and $R Q_1$ have this form $MK+P$ (obviously) and $\deg(P) < \dfrac{\deg (M)}{2}$ ?

-
Is $F$ a field or ring? –  user38268 Nov 19 '11 at 22:01
Is a ring Benjamin –  juaninf Nov 19 '11 at 23:03
$\deg(M)$ suggests $M$ is a polynomial, which suggests the $M_i$ are polynomials, which suggests $Q$ is a polynomial, in which case, what is $\sqrt Q$, and how can it be comparable to a rational number? –  Gerry Myerson Nov 19 '11 at 23:38
yes M, Q are polynomials, in the begin i write "Given the following congruences (all polynomials are in F[X])", about $\sqrt{Q}$, I corrects that expression now –  juaninf Nov 20 '11 at 2:30
Sorry, I'm still confused. $\sqrt Q$ isn't a polynomial, so what is its degree? and what kind of an object is $R(\sqrt Q)$? and what kind of object is $K$? –  Gerry Myerson Nov 20 '11 at 11:46

[REMARK: Another edit pending. I will recalculate the possibilities given the minor change to the question allowing equality in the degree constraints. Cannot do it right now, sorry. If anyone else feels like giving it a go, please!]

Assuming that I interpreted this correctly, what seems to be going on is the following.

Consider the congruence $$P(X)\equiv Q_1(X) R(X) \pmod {M(X)}.$$ Assume that $\deg M(X)=m$.

Assume that $Q_1(X)$ has degree $t$. For now we keep its coefficients as unknowns, and write $$Q_1(x)=a_0+a_1X+a_2X^2+\cdots+a_tX^T.$$ Consider the product $R(X) Q_1(X)$. Let us reduce it modulo $M(x)$. Because the polynomial $R(X)$ is known, the result of that reduction looks like $$R(X)Q_1(X)\equiv P(X)=p_0+p_1 X+p_2X^2+\cdots p_{m-1}X^{m-1}\pmod {M(X)},$$ where the coefficients $p_i, i=0,1,\ldots, m-1,$ are some known linear combinations of the coefficients $a_j, j=0,1,\ldots,t$. Let us extract the $t$ highest degree terms, and form the vector $$v(Q_1)=(p_{m-t},p_{m-t+1},\ldots,p_{m-1})\in F^t.$$ The relation $Q_1\mapsto v(Q_1)$ is an $F$-linear mapping from the $(t+1)$-dimensional space of polynomials of $F[X]$ of degree at most $t$ to the space $F^t$. By rank-nullity theorem it has a non-trivial kernel. Therefore there exists a non-zero choice of the polynomial $Q_1(X)$ such that the degree of the remainder $P(X)$ of $Q_1(X) R(X)$ modulo $M(X)$ is less than $m-t$.

If $m=2k+1$ is an odd integer, then we are constrained by $\deg Q_1<k$. In that case we can only guarantee to get $\deg P(X)<m-(k-1)=k+2$, which is a bit higher than what you asked for. Observe that the above bound on the degree of the remainder $P(X)$ is the best possible. For example (still in the case $m=2k+1$), if $R(X)=X^{k+1}$ gets multiplied by a polynomial $Q_1(X)$ of degree $<k$, we don't get any reduction mod $M(X)$, because the product is of degree $<2k+1$.

So it looks like a "near miss". If you can relax the degree constraints a bit (one may be enough?), then we might find solutions.

I have not even broached the problem of finding the polynomials $b_i(X)$, yet, because this major obstacle of degree constraints needs to be cleared up first. I don't foresee too serious problems there, because, by CRT, the ring $F[X]/(M(X))$ splits into a direct sum of $F(X)/(m_i(X))$, and these are all finite fields of characteristic two meaning that all the elements there have square roots.

-
Hi @Jyrki thanks by your time, I understand your answer for my question, ... but If the $m_i$ aren't only linear, my question could be yes?. pdta: I clarify my post –  juaninf Feb 1 '12 at 18:34
You write Anyway, this means that $b_i$ are uniquely determined $by P,R,mi$, but see that $P$ is unknow ... –  juaninf Feb 4 '12 at 6:55
@Juan, please tell us at the beginning, which quantities are known, and which are not! You said that the $b_i(X)$:s are unknowns, so I assumed that the rest are given. I don't know the original problem, so cannot tell. Also, you say that $y_i(X)$ is the multiplicative inverse of $M_i(x)$, but don't specify the ring, where this inverse relation is supposed to hold? Modulo $m_i(X)$? –  Jyrki Lahtonen Feb 4 '12 at 8:07
@Jyrky, thanks by your response, I modify a question and put the module $m_i(X)$ ... very thanks –  juaninf Feb 4 '12 at 8:45
@Juan, please also list those polynomials that are known. –  Jyrki Lahtonen Feb 4 '12 at 10:42

For example

$K[a] = GF(2),F[a] = GF(2^7),PR[X] = \operatorname{PolynomialRing}(F[a])$

Give

$M = (X + 1)(X + a^2 + a)(X + a^4 + a^3)(X + a^5)(X + a^5 + a^4)(X + a^6 + a + 1)(X + a^6 + a^5)$

\eqalign{R &= (a^6 + a^4 + a^3 + 1)X^6 + a^2X^5 + (a^6 + a^3 + a + 1)X^4 + (a^6 + a^2 + a + 1)X^3\cr &+ (a^6 + a^5 + a^3 + a^2 + a + 1)X^2 + (a^6 + a^5 + a^4 + 1)X + a^6 + a^3 + a + 1\cr}

Applying CRT (with $a_i$ than variables) get

\eqalign{QR^2&=((a^6 + a^4 + a^3 + a)X^{11} + (a^6 + a^5 + a)X^{10} + (a^5 + a^3)X^9 + (a^6 + a^3 + 1)X^8\cr &+ (a^6 + a^3 + a + 1)X^7 + (a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)X^6 + (a^6 + a^5)X^5 + (a^5 + a^3 + a)X^4\cr &+ (a^2 + a + 1)X^3 + (a^6 + a^5 + a^4 + a^2)X^2 + (a^6 + a^4 + a^2)X)(R^2)a_1 + ((a^6 + a^4 + a^3 + 1)X^{11}\cr &+ (a^6 + a^4 + a^3 + a^2)X^{10} + (a^6 + a^5 + a^4 + a + 1)X^9 + (a^4 + a^3 + a^2 + 1)X^8\cr &+ (a^6 + a^3 + a^2 + a)X^7 + (a^5 + a^4 + a^3)X^6 + (a^6 + a^3)X^5 + (a^6 + a^4 + a^3)X^4\cr &+ (a^2 + 1)X^3 + (a^6 + a^5 + a^3 + a^2 + a + 1)X^2 + (a^6 + a^4 + a^2 + a)X + a^5 + a^4 + 1)a_2R^2\cr &+ ((a^6 + a^5 + a^2 + 1)X^{11} + (a^4 + a^3 + a^2 + 1)X^{10} + (a^5 + a^4 + a^2)X^9\cr &+ (a^5 + a^4 + a^3 + 1)X^8 + (a^6 + a^2 + 1)X^7 + (a^5 + a^4 + a^2 + 1)X^6 + (a^5 + a^4 + a^3 + 1)X^5\cr &+ (a^4 + a^3 + a)X^4 + (a^6 + a^5 + a^3 + 1)X^3 + (a^5 + a^4 + a^3)X^2 + (a^6 + a^4 + a^3 + a^2 + 1)X\cr &+ a^5 + a^3 + a)a_3R^2 + ((a^4 + a^2 + a)X^{11} + (a^5 + a^3 + 1)X^{10} + (a^5 + a^3 + a^2 + a)X^9\cr &+ (a^5 + a^4 + a)X^8 + (a^4 + a^3 + a^2 + a + 1)X^7 + (a^4 + a^3 + a^2)X^6 + (a^3 + a^2)X^5 + (a^6 + a^4 + a^3 + a)X^4\cr &+ (a^4 + a^3 + a^2 + a)X^3 + (a^5 + a^4 + a + 1)X^2 + (a^5 + a^4 + a^3 + a + 1)X + a^6 + a^5)a_4R^2\cr &+ ((a^5 + a^4 + a^3 + a^2)X^{11} + (a^5 + a^4 + a^3 + a^2)X^{10} + (a^6 + a^2 + a + 1)X^9\cr &+ (a^6 + a^2 + a + 1)X^8 + (a^5 + a^4 + a)X^7 + (a^5 + a^4 + a)X^6 + (a^6 + a^4 + a^3 + 1)X^5\cr &+ (a^6 + a^5 + a^4 + a^2)X^4 + a^5X^3 + (a^6 + a^2 + 1)X^2 + (a^6 + a^5 + a^4 + a^3 + a)X\cr &+ a^5 + a^4 + a^3 + a^2 + 1)a_5R^2 + ((a^6 + a^3)X^{11} + (a^5 + a^4 + a^2 + 1)X^{10} + a^5X^9\cr &+ (a^6 + a + 1)X^8 + (a^4 + a^2 + 1)X^7 + (a^6 + a^5 + a^4 + a^3 + a^2 + a)X^6 + (a^6 + a + 1)X^5\cr &+ (a^5 + a^2 + 1)X^4 + (a^4 + a^2 + a + 1)X^2 + X + a^2 + 1)a_6R^2 + (a^2X^{11} + (a + 1)X^{10}\cr &+ (a^5 + a^2 + a)X^9 + (a^6 + a^4 + a^3 + a + 1)X^8 + (a^6 + a^5 + a^4 + a^3)X^7 + (a^5 + a)X^6\cr &+ (a^2 + a)X^5 + (a^6 + a^3 + a^2 + a + 1)X^4 + (a^6 + a^4 + a^2 + 1)X^3 + (a^6 + a)X^2\cr &+ (a^6 + a^5 + a^4)X + a^3 + a^2 + a)a_7R^2\cr},

and obviously I don't resolved this quadratic equation, because i want know the $a_i$'s values, but I will expect this expression :

$P\equiv{Q_1R}\pmod{M}$

My question: Is there any mode to choose $a_i$ where $\operatorname{degree}(Q_1) < \dfrac{\deg (M)-1}{2}$ and $R(Q_1)$ have this form $MK+P$ (obviously) and $\deg(P) < \dfrac{\deg (M)}{2}$ ?

pdta: that $a_i$ variables, I don't see in this browser, :(, anyelse, know how I forced this expression than wrapper?

-