在java中使用擴展的euclid計算多項式逆

我正在嘗試了解 NTRU-PKCS，因此我想編寫一個幼稚的版本。現在我的問題：

我試圖用歐幾里得算法的擴展版本計算多項式的逆。對於某些多項式，我的程式碼可以正常工作，但是當我嘗試使用 NTRU-PKCS-Tutorial NTRU-PKCS-Tutorial 中的範例時，它會失敗。參數是 $ N=11 $ 和 $ q = 32 $ ; 多項式 $ f $ 是：

$ \begin{equation} f= -x^{10}+x^9+x^6-x^4+x^2+x-1 \end{equation} $

$ \begin{equation} f^{-1} \text{ mod }q = 30x^{10}+18x^9+20x^8+22x^7+16x^6+15x^5+4x^4+16x^3+6x^2+9x+5 \end{equation} $

我真的不知道為什麼我的程式碼不產生正確的 $ f^{-1} $ …

我的程式碼：

   public PolynomialMod inverse(int N, int mod) {
   int loop = 0;
   PolynomialMod G = PolynomialMod.ZERO.clone();
   G.setNMod(N, mod);
   PolynomialMod newG = (PolynomialMod) PolynomialMod.ONE.clone();
   newG.setNMod(N, mod);
   int[] coeffR = { 1, 1, 0, 1, 1, 0, 0, 0, 1 };

   PolynomialMod quotient = null;
   PolynomialMod newR = this.clone();
   PolynomialMod R = this.getRing(N, mod);
   R.setNMod(N, mod);
   newR.setNMod(N, mod);

   while (!newR.equalsZero()) {
       if (DEBUG && loop != 0)
           System.out.println("loop: " + loop);
       if (DEBUG && loop == 0)
           System.out.println("========Initial Values========");
       if (DEBUG)
           System.out.println("R   : " + R);
       if (DEBUG)
           System.out.println("newR: " + newR);
       if (DEBUG)
           System.out.println("Quotient: " + quotient);
       if (DEBUG)
           System.out.println("G   : " + G);
       if (DEBUG)
           System.out.println("newG: " + newG);
       if (DEBUG && loop == 0)
           System.out.println("========Initial Values========");
       if (DEBUG)
           System.out.println("\n");

       quotient = R.div(newR)[0];
       PolynomialMod help = R.clone();
       R = newR.clone();
       PolynomialMod times = quotient.times(newR);
       times.reduceBetweenZeroAndQ();
       newR = help.sub(times);
       newR.deleteLeadingZeros();
       newR.degree = newR.values.size() - 1;
       help = G.clone();
       G = newG.clone();
       PolynomialMod times2 = quotient.times(newG);
       times2.reduceBetweenZeroAndQ();
       newG = help.sub(times2);
       loop++;

   }
   if (R.getDegree() > 0)
       throw new ArithmeticException("irreducible or multiple");

   return G.div(R)[0];
}

輸出：

========初始值======== R：

$$ -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 $$新R：$$ -1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1 $$商：空 G

：$$ 0 $$新G：$$ 1 $$ ========初始值======== 循環：1 R：

$$ -1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1 $$新R：$$ 30, 0, 2, 1, 31, 31, 1, 1, 0, 1 $$商：$$ 31, 31 $$G ：$$ 1 $$新G：$$ 1, 1 $$ 循環：2 R：

$$ 30, 0, 2, 1, 31, 31, 1, 1, 0, 1 $$新R：$$ 1, 31, 31, 1, 1, 0, 31, 0, 1 $$商：$$ 1, 31 $$G ：$$ 1, 1 $$新G：$$ 0, 0, 1 $$ 循環：3 R：

$$ 1, 31, 31, 1, 1, 0, 31, 0, 1 $$新R：$$ 30, 31, 3, 2, 30, 30, 1, 2 $$商：$$ 0, 1 $$G ：$$ 0, 0, 1 $$新G：$$ 1, 1, 0, 31 $$

它發生了，當我第四次循環時，因為我必須計算 $ 2 * x = 1 \text{ mod }32 $ ，但不存在這樣的逆 $ 2 \text{ mod }32 $ . 所以錯誤必鬚髮生在之前，但我真的不知道它發生在哪裡。

---

編輯：

這個錯誤並不是真正的編碼問題，因為當我用“筆和紙”計算它時，我得到了完全相同的問題……

這就是為什麼我對擴展歐幾里得的理解一定有問題，但我不明白為什麼……

R_0:= x^N -1 
R_1:= f
R_n+1:= R_(n)- R_(n-1) div R(n-2) 

對我來說看起來不錯：/

編輯2：

感謝您引用stackoverflow執行緒，我將它編碼為虛擬碼，但它在完全相同的步驟中失敗:(這是我的新程式碼：

   public void inverseEuclid(int N, int mod) {
   PolynomialMod a= this.clone();
   PolynomialMod b= getRing(N,mod);
   PolynomialMod u = PolynomialMod.ONE.clone();
   u.setNMod(N, mod);
   PolynomialMod v1 = PolynomialMod.ZERO.clone();
   v1.setNMod(N, mod);
   PolynomialMod d = this.clone();
   PolynomialMod v3 = b.clone(); 

   while(!v3.equalsZero()) {
       System.out.println("========values========");
       System.out.println("d : "+d);
       System.out.println("v3: "+v3);
       PolynomialMod [] div = d.div(v3);
       PolynomialMod q =  div[0].clone();
       System.out.println("q : "+q);
       PolynomialMod t3 =  div[1].clone();
       System.out.println("t3: "+t3);
       PolynomialMod t1 = u.sub(q.convolution(v1));
       System.out.println("t1: "+t1);
       System.out.println("========values========\n\n");

       u = v1.clone();
       d = v3.clone();
       v1= t1.clone();
       v3=t3.clone();

       u.deleteLeadingZeros();
       d.deleteLeadingZeros();
       v1.deleteLeadingZeros();
       v3.deleteLeadingZeros();
   }
   PolynomialMod v = d.sub(a.convolution(u)).div(b)[0];
   System.out.println("u: "+u);
   System.out.println("v: "+v);
   System.out.println("d: "+d);
}

這是我的歐幾里得除法程式碼。我知道這不是一個編碼論壇，但我嘗試了 euclid 的實現，並且我在紙上做了，同樣的錯誤正在發生……也許有人知道我做錯了什麼……

   public PolynomialMod[] div(final PolynomialMod other) {
   if (other.isZero())
       throw new ArithmeticException("division by zero");
   final int degreeDifference = this.getDegree() - other.getDegree() + 1;
   if (degreeDifference <= 0)
       return new PolynomialMod[] { PolynomialMod.ZERO, this };

   final PolynomialMod rest = this.clone();
   final PolynomialMod quotient = new PolynomialMod(degreeDifference - 1, N, mod);
   final int otherDegree = other.getDegree();
   final int coeff = other.values.get(otherDegree);
   for (int i = degreeDifference - 1; i >= 0; i--) {
       final int q = MyMath.divMod(rest.values.get(otherDegree + i), coeff, mod);

       quotient.values.set(i, q);
       for (int j = 0; j <= otherDegree; j++) {
           int restHelp = ((rest.values.get(i + j) - q * other.values.get(j)) + mod) % mod;
           rest.values.set(i + j, restHelp);
       }
   }
   return new PolynomialMod[] { new PolynomialMod(quotient.values, N, mod),
           new PolynomialMod(rest.values, N, mod) };
}

新R：

$$ -1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1 $$

這個多項式是 $ f = -x^{10} + x^9 + x^6 - x^4 + x^2 + x - 1 $ 你想要的地方：

$ f=x^{10}+x^9+x^6−x^4+x^2+x−1 $

的標誌 $ x^{10} $ 對面。

您的算法/程式碼實際上是正確的。請參閱 sage 的以下計算：

sage: f

-x^10 + x^9 + x^6 - x^4 + x^2 + x - 1

sage: f_inv

30*x^10 + 18*x^9 + 20*x^8 + 22*x^7 + 16*x^6 + 15*x^5 + 4*x^4 + 16*x^3 + 6*x^2 + 9*x + 5

sage: (f*f_inv)%(x^11-1)%32

1

問題如下：

該程式碼適用於多項式 f(x) mod p，其中 p 是素數（或 gcd(p,coeff(f(x))) = 1），但我想要反模 32，實際上是：2^5 ，所以我必須計算逆模 2，然後將其提升到 2^5

解決方案線上程中：多項式的逆

引用自：https://crypto.stackexchange.com/questions/37063