1
$\begingroup$

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}$ ?

  • 0
    @JyrkiLahtonen thanks :D2012-02-07

2 Answers 2

2

[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. In that case we can only guarantee to get $\deg P(X), 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 $, 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.

  • 0
    @Juan. If you say so :-) I don't remember. I once wrote a program to decode certain kinds of Goppa codes, and I used a different algorithm. So I don't remember how this goes with alternant codes, and don't have the time to look it up now. The inclusion of equality will probably change the solvability of those equations quite a bit.2012-02-07
1

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?