1
$\begingroup$

I am very new to the world of cryptography and have just began my research in the post quantum cryptography sector. I have been reading and trying to understand NTRU key generation and am struggling to understand how to practically do the inverse of f. I know that this is solved using the Euclidean algorithm, but I am unable to figure out what the steps would be. I was hoping someone would be able to show the steps to solve the example shown on the NTRUEncrypt wiki page shown below (fp or fq), or a smaller polynomial that gets the point across. I am more interested in the practical steps then the theory behind it, as I have found many resources for that.

Thank you!

NTRU inverse

$\endgroup$
1
  • 1
    $\begingroup$ It is found by the Extended-GCD. If you write "find polynomial inverse modulo" these words into your search engine you will see. Almost all books mentions this, too. See from handbook applied cryptography page 82 $\endgroup$ – kelalaka Mar 4 at 7:46
1
$\begingroup$

I'll try to follow a similar notation to the example on wikipedia

Our initial inputs are $p(x) = x^{11}-1$ which defines the ring and $a(x)=-x^{10}+x^9+x^6-x^4+x^2-1$ and working mod 3 rather than the mod 2 example on wikipedia.

For step 1 we have quotient $q_1(x)=2x+2$ and remainder $r_1(x)=x^9+x^7+x^6+2x^5+2x^4+x^3+2x^2+1$ so that $t_1=x+1$.

For step 2 we have quotient $q_2=2x+1$ and remainder $r_2=x^8+2x^6+x^4+x^3+2x^2+2x+1$ and $t_2=x^2$.

For step 3 we have quotient $q_3=x$ and remainder $r_3=2x^7+x^6+x^7+x^4+2x^3+2x+1$ and $t_2=x^3+x+1$.

For step 4 we have quotient $q_4=2x+2$ and remainder $r_4=x^6+2x^5+x^4+x^2+2x+2$ and $t_4=2x^4+2x^3+2x^2+2x+1$.

For step 5 we have quotient $q_5=2x$ and remainder $r_5=2x^5+x^4+2x^2+x+1$ and $t_5=2x^5+2x^4+x^3+2x^2+2x+1$.

For step 6 we have quotient $q_6=2x$ and remainder $r_6=x^4+2x^3+2x^2+2$ and $t_6=x2x^6+2x^5+x^3+x^2+1$.

For step 7 we have quotient $q_7=2x$ and remainder $r_7=2x^3+2x^2+1$ and $t_7=x2x^7+2x^6+2x^5+2x^3+2x^2+1$.

For step 8 we have quotient $q_8=2x+2$ and remainder $r_8=x^2+x$ and $t_9=2x^9+x^8+2*x^7+x^5+2x^4+2x^3+2x+1$.

For step 9 we have quotient $q_9=2x$ and remainder $r_9=1$ and $t_9=2x^9+x^8+2x^7+x^5+2x^4+2x^3+x+2$, which is the required inverse.

I'll leave the mod 32 example as an exercise (sagemath is your friend).

$\endgroup$
2
  • $\begingroup$ Thank you, this is what I was hoping to see, I think I was using a invalid polynomial for my p(x). Thank you for your input! $\endgroup$ – Daftyler Mar 4 at 19:16
  • $\begingroup$ Thanks, this has been useful for me too. I have a follow-up question: so the Euclidean algorithm usually only runs in Euclidean domains (ED) and when working mod 3 you're running it in $\mathbb{Z}_3[X]$ (right?) which I see is an ED because $\mathbb{Z}_3$ is a field. But if you're working mod 32, then could there be problems as $\mathbb{Z}_{32}[X]$ is no longer an ED? $\endgroup$ – dcw May 29 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.