I have a paper that describes an algorithm for finding the inverse of a polynomial in $(\mathbb{Z}/3\mathbb{Z})[X]/(X^N-1)$:
I want to implement it in code, but I'm having difficulties to understand it. I hope someone could answer me the following questions to clarify mu dubts:
-
The paper specifies that all computations are done modulo 3, and thus the coefficients are choosen from the set $\{-1,0,1\}$. Is it because we are talking about $\mathbb{Z}/3\mathbb{Z}$? Some implementations in code seem to use coefficients in the set $\{0,1,2\}$. Is there any difference or are these sets equivalent?
-
Step 4 involves a division and multiplication by $X$. I think that dividing by $X$ means multiplying by the inverse of $X$, but I don't know if that inverse should be calculated modulo 3 or if it is the inverse of $X$ in the stated ring. Same question applies to the star multiplication by $X$.
Thanks in advance for any answer.
Best Answer
$X$ is not a variable ranging over $\Bbb{Z}_3$. It is an indeterminate. So division by $X$ should be polynomial division (division modulo three is meaningless). Think about the situation in Step 3. You have a polynomial $f(X)$. If $f_0=0$ it means that the constant term of $f(X)$ is zero. So at this step you are required to, for example, divide $$f(X)=X-X^2+X^5-X^6$$ by $X$, and come up with $f(X)/X=1-X+X^4-X^5$. Or, taking into account the do-while loop, divide something like $$f(X)=X^4+X^5+X^6-X^{11}$$ by $X$ four times to end up with $1+X+X^2-X^7$. The point is that when exiting this loop $f(X)$ must have a non-zero constant term.
If you store a polynomial as an array of its coefficients, division by $X$ amounts to stripping the leading zeros from that array (and padding them to the high degree end).
In the step where you are to multiply $c(X)$ by $X$ you must take care not to let the array of coefficients of $c(X)$ overflow from the high end. The algebra is done modulo $X^N-1$, meaning that if $c(X)*X$ get a term of degree $N$, you reduce it modulo $X^N-1$, whence $X^N=1$. So if you represent $$c(X)=c_0+c_1X+c_2X^2+\cdots+c_{N-1}X^{N-1}$$ with the array $(c_0,c_1,\ldots,c_{N-1})$, then $c(X)*X$ becomes the array $(c_{N-1},c_0,c_1,\ldots,c_{N-2})$. In other words, multiplication by $X$ amounts to a cyclic shift to the right for the list of coefficients.