1
$\begingroup$

I cannot find whether multiplicative inverse of $x^3+x^2+x+1 \pmod{x^5+x^4+x^3-x^2-x+1}$ over $\mathrm{GF}(3)$ exists. This problem must be solved with Extended Euclidean algorithm.

I tried to divide $x^5+x^4+x^3-x^2-x+1$ by $x^3+x^2+x+1$.

I think I divided it wrong. I got $x^2-2x-2$.

Thanks for any help

  • 0
    If it's too much work / too error prone, then don't bother doing a complete division: you can make progress even if all you compute is the leading term of the quotient, which can be obtained by inspection.2012-05-27

1 Answers 1

2

The problem you are trying to solve is not clearly stated, but what is clear is that you are having some difficulty with polynomial division, or (more likely) just think that you are. What probably happened is something that happens to everybody, a slip with signs.

We will do ordinary polynomial division. To start the division process, imitate school division. The polynomial $x^3+x^2+x+1$ "goes into" $x^5+x^4+x^3-x^2-x+1$ how many tines? Clearly $x^2$ times. So multiply $x^3+x^2+x+1$ by $x^2$, subtract from $x^5+x^4+x^3-x^2-x+1$. The raw remainder we get is $-2x^2-x+1$. Since we are working over the $3$ element field, this can be rewritten in various ways. It is sensible to replace the $-2$ by $1$, obtaining remainder $x^2-x+1$, or $x^2+2x+1$.

If negatives give you trouble, you could start by replacing $x^5+x^4+x^3-x^2-x+1$ by $x^5+x^4+x^3+2x^2+2x+1$.

Anyway, we have quotient $x^2$, remainder $x^2-x+1$. Continue the Euclidean algorithm process by dividing $x^3+x^2+x+1$ by $x^2-x+1$. You should get quotient $x+2$ (or $x-1$), remainder some version of $2x-1$. Continue.

  • 0
    @Dilip But then it is *not* the mult. inverse of "a polynomial" in that field, but of an element of it which, I agree, can be represented by a polynomial-like element...2012-05-27