0
$\begingroup$

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...?

enter image description here

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?

$\endgroup$
4
  • $\begingroup$ To be clear; you are trying to find $f^{-1}$ such that $f\cdot f^{-1}\equiv1\pmod{q}$? $\endgroup$
    – Servaes
    Commented Nov 29, 2021 at 10:46
  • $\begingroup$ Yes, but specifically with that algorithm (I corrected the link in the question, which was broken before). $\endgroup$
    – maciek
    Commented Nov 29, 2021 at 10:47
  • $\begingroup$ It's much better to do the extended algorithm this way. Also this makes it much easier to find the error (find the first RHS equation that fails). $\endgroup$ Commented Nov 29, 2021 at 11:16
  • $\begingroup$ please do not post pictures of text but use Latex $\endgroup$
    – miracle173
    Commented Nov 29, 2021 at 13:42

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The way I understand this is that both $r=3$ and $r=0$ are constant polynomials and that's where I should end. Otherwise, once I iterated the algorithm once again I still obtained sth different then expected... I get $t = 3 \times x^5 + 2$ and then indeed $r=0$ $\endgroup$
    – maciek
    Commented Nov 29, 2021 at 13:17
  • $\begingroup$ @maciek I just noticed that the algorithm you link has while r ≠ 0 do, but you do not end with $r=0$. That's all I know, I can't be bothered to trace the steps of the algorithm to see what goes wrong, unfortunately. $\endgroup$
    – Servaes
    Commented Nov 29, 2021 at 19:21
0
$\begingroup$

I have tested out a few examples and indeed, the answer I have added in my Note by Mr. Takeuchi works out in practice. Generally speaking, extended euclidean algorithm for polynomial division in rings modulo $n$ should end not when r == 0 but when $r \in \{0,...,n-1\}$, that is when we reach a polynomial of degree 1. Let's say that the algorithm ended with $r = x$, $x \neq 1$ and we obtained a polynomial $t$ which we expected to be the inverse polynomial $f^{-1}$. What one should do then is to find the $x^{-1}$ so we have $x \times x^{-1} = 1$. What is then left to do is to multiply coefficients of $t$ by the same value to obtain the inverse we seek: $t \times x^{-1} = f^{-1}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .