F模p的逆NTRU欧几里德算法

Question

我对密码学很陌生，刚刚开始对后量子密码学领域的研究。我一直在阅读和尝试理解NTRU的密钥生成，我很难理解如何实际地做f的逆，我知道这是用欧几里德算法解决的，但我不知道步骤是什么。我希望有人能够给出解决下面NTRUEncrypt wiki页面(fp或fq)上显示的示例的步骤，或者用一个更小的多项式来解决这个问题。我更感兴趣的是实际步骤，而不是背后的理论，因为我已经找到了很多资源。

谢谢!

Answer 1

我将尝试遵循类似的维基百科的例子表示法

我们最初的输入是p(x) = x^{11}-1，它定义了环和a(x)=-x^{10}+x^9+x^6-x^4+x^2-1以及工作模式3，而不是维基百科上的mod 2示例。

对于步骤1，我们有商q_1(x)=2x+2和余数r_1(x)=x^9+x^7+x^6+2x^5+2x^4+x^3+2x^2+1，因此t_1=x+1。

对于步骤2，我们有商q_2=2x+1和余数r_2=x^8+2x^6+x^4+x^3+2x^2+2x+1和t_2=x^2。

对于步骤3，我们有商q_3=x和余数r_3=2x^7+x^6+x^7+x^4+2x^3+2x+1和t_2=x^3+x+1。

对于步骤4，我们有商q_4=2x+2和余数r_4=x^6+2x^5+x^4+x^2+2x+2和t_4=2x^4+2x^3+2x^2+2x+1。

对于步骤5，我们有商q_5=2x和余数r_5=2x^5+x^4+2x^2+x+1和t_5=2x^5+2x^4+x^3+2x^2+2x+1。

对于步骤6，我们有商q_6=2x和余数r_6=x^4+2x^3+2x^2+2和t_6=x2x^6+2x^5+x^3+x^2+1。

对于步骤7，我们有商q_7=2x和余数r_7=2x^3+2x^2+1和t_7=x2x^7+2x^6+2x^5+2x^3+2x^2+1。

对于步骤8，我们有商q_8=2x+2和余数r_8=x^2+x和t_9=2x^9+x^8+2*x^7+x^5+2x^4+2x^3+2x+1。

对于步骤9，我们有商q_9=2x和余数r_9=1和t_9=2x^9+x^8+2x^7+x^5+2x^4+2x^3+x+2，这是所需的逆。

我将把mod 32示例作为练习(sagemath是您的朋友)。