How to solve binary equation which has mod?

438 Views Asked by At

Three messages in binary format are sent $$ a_0 a_1 a_2 a_3 $$ and coded in binary format $$b_0 b_1 b_2 b_3 b_4 b_5 b_6$$ Symbols $$b_0,b_1,b_2,b_3,b_4,b_5,b_6$$ are the coefficients of the Boolean polynomial $$B(x) = b_0\oplus b_1x\oplus b_2x^2\oplus b_3x^3\oplus b_4x^4\oplus b_5x^5\oplus b_6x^6$$ which is calculated according to the formula $$B(x) = A(x) * x^3 \oplus A(x) * x^3 mod (1 \oplus x\oplus x^3)$$ $$A(x)= a_0 \oplus a_1x \oplus a_2x^2 \oplus a_3x^3$$

Each of the messages can have one mistake or no mistakes. The messages: 0010011, 0101111, 1001100.

How to find encoded messages ?

I can try to find a solution outright( for the first message) and I get this equation( I equated B(x) and B(x) and set coefficients from the first message): $$b_2x^2\oplus b_5x^5\oplus b_6x^6 =( a_0 \oplus a_1x \oplus a_2x^2 \oplus a_3x^3) * x^3 \oplus (a_0 \oplus a_1x \oplus a_2x^2 \oplus a_3x^3 )* x^3 mod (1 \oplus x\oplus x^3)$$ But I don't know how to solve this equation.

1

There are 1 best solutions below

0
On BEST ANSWER

Construct first the table of remainders modulo $f = 1 + x + x^3$ of all monomials. $$ \begin{matrix} \text{monomial} & \text{remainder}\\ 1 & 1\\ x & x\\ x^2 & x^2\\ x^3 & 1 + x\\ x^4 & x + x^2\\ x^5 & 1 + x + x^2\\ x^6 & 1 + x^2\\ \end{matrix} $$

Consider the first example $0010011$. Associate to it the polynomial $$ B = x^2 + x^5 + x^6. $$ Do long division by $f$ to obtain the remainder $$ x + x^2. $$ This is different from zero, thus an error has occurred. Assuming exactly one error occurred, by the table above it occurred in the position $x^4$, so the correct $7$-bit message was $0010111$, and the original 4-bit message was $0111$.

Do the same for the other two messages $0101111, 1001100$. For the first one the remainder is $1 + x^2$, so the correct $7$-bit message is $0101110$. For the second one the remainder is $x^2$, so the correct $7$-bit message is $1011100$.