Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
show 19 more comments

2 Answers 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<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.

share|improve this answer
    
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
show 5 more comments

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?

share|improve this answer
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.