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
    Is $F$ a field or ring?2011-11-19
  • 0
    Is a ring Benjamin2011-11-19
  • 1
    $\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?2011-11-19
  • 0
    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 now2011-11-20
  • 0
    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$?2011-11-20
  • 0
    Hi Gerry all are polynomials over F[X], $\sqrt{Q}$, is a polynomial, .. $R\sqrt{Q}$ too is a polynomial, K,P,R are a polynomials2011-11-20
  • 0
    Maybe you had better give an example. I'm just not seeing how $\sqrt Q$ is going to be a polynomial.2011-11-21
  • 0
    Gerry thanks by your attention I edit the post, ... you understand now?2011-11-21
  • 0
    It is still very confusing. It is not clear which things are given (the $a_i$ and the $m_i$ only?). $M$ is never defined, but I presume it's the product of the $m_i$. Maybe $R(Q_1)$ is supposed to be $R{\it\ times\ }Q_1$. I repeat my plea for an example.2011-11-21
  • 0
    yes R*Q1, ... example below2011-11-21
  • 0
    The example you posted below should have been an edit to your question, not an answer. I attempted to improve the formatting; there is still much room for improvement. But in any event, as an example, it is useless. Examples intended to clarify things should be as simple as possible, not as complicated as possible. But it's worse than that. What does $K[a]=GF(2)$ mean, when $K$ has only been defined by $RQ_1=MK+P$ and $a$ hasn't been defined at all?2011-11-21
  • 0
    Gerry thanks by your time, ... now I edit again the post, ...2011-11-21
  • 0
    Well, we're getting closer. It would be nice to have an example which you *can* solve, so we can see what you are looking for in a solution. Meanwhile, you told Benjamin that $F$ was a ring, but in your example it's a field, the field of 16 elements. Also, if we forget about the $a_i$ and just look at the following problem: given $Q$ and $M$, find $Q_1$ such that $Q_1^2\equiv Q\pmod M$, you are aware that that could have many, many solutions? Perhaps even infinitely many, depending on the ring $F$?2011-11-21
  • 0
    no Gerry, in my example $K_2$ is a field, $F$ is a ring, ... Gerry What's $a_i$ you say?, ... about your problem, yes I aware that could have many solutions, but $Q_1$ and $P$ will should match with the conditions given in my question.2011-11-21
  • 0
    dont forget this question please2011-11-23
  • 0
    I haven't forgotten it, I just can't make head or tail of it. Please, an example where you *can* solve it, or at least some good reason why you think it should be possible to solve it.2011-11-24
  • 0
    @Juan, the question may be interesting, but it is badly formatted. You should **begin** by describing that $F=K_2[a]$ is the field of 16 elements, give the minimal polynomial of $a$ (there is no canonical choice, you have to tell us which) and so on. You have to first tell what the $m_i$_s are, and then what $M$ is (sounds like it is their product). Also, you keep using both $F$ and $K_2[a]$. Unless they mean the same thing, then I'm totally lost. Furthermore $F[x]/M$ is a direct product of copies of $F$, and squaring is a bijection in $F$, so the problem should be easy. **EDIT THE QUESTION**2011-12-25
  • 0
    ... like what is $a$? I guess it depends on the context. But you should realize that $F=GF(16)=K_2[a]$, then $a$ cannot be an unknown quantity. It must have a minimial polynomial for starters. Furthermore $F$ is then a field. Not just a ring. The impression I get that you are very confused about some things underlying your problem, and you really don't understand what you are asking. We certainly don't! I guessed, but we hate to guess (unless we are fairly confident about the intended meaning).2011-12-25
  • 0
    thanks, by your responses @Jyrki, I am writing the question again.2012-01-12
  • 0
    @Juan, I made an attempt to reformulate your question. Please check, whether this is what you really wanted to ask? I honestly think that a better way attackinf this problem is to first look for $P$ and $Q_1$ and only then start worrying about the $b_i$s. If you are not happy with my interpretation, it is, of course, your call to roll the question back to an earlier version. In that case do edit to a form, where you first tell us the known quantities.2012-02-05
  • 0
    @Juan, I edited my answer to reflect my current understanding of what you wanted to ask. Looks like a near miss to me. Say, if $M$ is cubic, we need to allow $Q_1$ of degree equal to $(3-1)/2$ in order to get a linear remainder $P$. Please check, whether you really want $\le$ instead of $<$ in one of the degree constraints. It is a near miss.2012-02-06
  • 0
    @JyrkiLahtonen $\deg(Q_1) \leq \dfrac{\deg (M)-1}{2}$, $\deg(P) \leq \dfrac{\deg (M)}{2}$, I can edit yor new formulation?2012-02-07
  • 0
    Of course you can edit! It's still your question:-)2012-02-07
  • 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

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
    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 post2012-02-01
  • 0
    You write Anyway, this means that $b_i$ are uniquely determined $by P,R,mi$, but see that $P$ is unknow ...2012-02-04
  • 0
    @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)$?2012-02-04
  • 0
    @Jyrky, thanks by your response, I modify a question and put the module $m_i(X)$ ... very thanks2012-02-04
  • 0
    @Juan, please also list those polynomials that are known.2012-02-04
  • 0
    @Jyrky only $M(X)$ and $R(X)$2012-02-04
  • 0
    thanks by your time, you new formulation question is good, I am study the key equation of Alternant codes, this is why I make this question, ... the other constraints is $R(X)2012-02-07
  • 0
    @Juan, ahh! Yeah, I did notice that the degree constraints have the air of a key equation, but I am very rusty about the Alternant codes. My exposure being limited to RS-codes and Goppa codes. But is it not a common theme in key equations that we have some extra information about the syndrome. For example, we assume that it comes from a uniquely decodable error pattern? Is that the origin of your degree constraints here?2012-02-07
  • 0
    i don't understand when you say " we assume that it comes from a uniquely decodable error pattern", ... $R(X)$ is a syndrome in alternant or Goppa codes the constraints is that $deg(R(X))2012-02-07
  • 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?