I am trying to follow an algorithm but I cannot get the correct result. I don't know if the calculations are wrong (would be surprised, since I checked them carefully with an online SageMath engine), did I pick wrong polynomials or maybe I misunderstood something in the algorithm…
My task is to find a multiplicative inverse of a polynomial $f$ modulo polynomial $q$; standard operation while dealing with finite fields. Here we work in $\Bbb{Z}/5\Bbb{Z}$, coefficients are mod $5$ and max degree of a polynomial is 5. I picked rather simple examples and also checked online that indeed $f$ in invertible and I know what $f^{-1}$ should be. I would like to follow the extended euclidean algorithm, as described here: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode … (I am keeping the variable names the same for brevity). The algorithm converges quickly, as expected, and it looks reasonable as I proceed with it but the result polynomial I get is definitely not an inverse of $f$…
Am I doing something wrong here? Or are the initial polynomials wrong…?
Observation
What I get now (with the current $t$) is $3$ $mod q$.
However, if I'd multiply it by 2 I see that: $t \times 2 = f^{-1}$ and $3 \times 2 = 1$.
Am I missing a multiplication by 2(?)
Note
I might be missing the last iteration of the algorithm(?)
If so then I calculate: $[4x+3] / [3] = [3x + 1]$ and the new $r=0$
In such case: $t = 3x^5 + 2$, which is also wrong…
Note
I asked this question on a facebook group and a fellow member, Kiyoshi Andres Takeuchi, explained to me:
In a more general setting, your algorithm ends when it gets to the gcd. Now, with integers, the gcd could be 1,…,n if we insist on positive numbers. There is not much problem because there are only two invertible elements in the integers, 1 and -1, so the choice is binary. I.e. we could've as easily said that the gcd of 12 and 9 is -3. Now, with coefficients in z/5z, we have the problem that there are more units. So while we only had two choices for gcd in the integers, with coefficients in z/5z we have 4 possibilities. Do you see where I'm going? The algorithm terminated when it reached 3, because there isn't much distinction between 1,2,3,4. They are the same number (up to units). This is a very common occurrence in commutative algebra. So to summarize, your algorithm ends when it finds a gcd up to units, and if you want to implement code that gives you exactly 1, you need to account for the possibility that you will get any of 1,2,3,4, and more generally for a non-invertible gcd, 1,2,3,4 * gcd.
This would imply that $r=3$ is in fact where the iteration should halt and I found the gcd polynomial. Now, to find the inverse I need to account for the modular multiplication by a scalar and adjust such that I have in fact $ = 1 mod q$, that would be the inverse polynomial. Is that correct?
Best Answer
I haven't checked your work, as I don't understand any of it, but the expression that you have found for $f^{-1}$ satisfies \begin{eqnarray*} f\cdot f^{-1}&=&(X^2+X+1)(4X^4+2X^3+4X^2+4X+2)\\ &=&4X^6+6X^5+10X^4+10X^3+10X^2+6X+2,\\ \end{eqnarray*} which shows that $$f\cdot f^{-1}\equiv3\pmod{q}.$$ In particular it seems that your $f^{-1}$ is off by a factor of $2$. Perhaps you are missing the last iteration in the algorithm; you do not yet have $r=0$.
Also note that in $\Bbb{Z}/5\Bbb{Z}$ you have $q=(x-1)^5$ and so the quotient is not a field. That is, not every polynomial has an inverse with respect to $q$. This particular polynomial $f$ does, however.