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