拡張ユークリッドアルゴリズムJAVA RSA

Question

私はEEAを実装しようとしています。私もこのパターンを見つけました。

extended_euclid(a,b) 
1 if b = 0 
2  than return (a,1,0) 
3 (d',s',t') <-- extended_euclid(b, a mod b) 
4 (d,s,t) <--- (d',t',s' - (a div b)t') 
5 return (d,s,t) 

は、そして、私のコードは次のようになります。私のコードが正しい場合

public static Triple extendedEuclid(BigInteger a, BigInteger b) { 
    if (b.equals(new BigInteger("0"))) { 
     return new Triple(a, new BigInteger("1"), new BigInteger("0")); 
    } else { 
     Triple i = extendedEuclid(b, a.mod(b)); 
     return new Triple(i.getA(), i.getB(), (i.getC().divide(i.getB()).multiply(i.getC()))); 
    } 
} 

- 私はかなり確実ではありません。私は20ほどのページを見上げましたが、まだそれを取得していません。私は精神的に固執している。おかげさまで

Answer 1

最終的な返品に失敗したようです。また、Tripleの3番目の値を間違って実装しました。ここに私の実装があります。 （私はまた、明確にするために、変数の名前を変更+のBigIntegerのヘルパー定数/方法を使用する。）

public class ExtendedEuclidAlgorithm { 
    public static void main(final String[] args) { 
     System.out.println("eea(240, 46) = " + apply(BigInteger.valueOf(240), BigInteger.valueOf(46))); 
     System.out.println("eea(65, 40) = " + apply(BigInteger.valueOf(65), BigInteger.valueOf(40))); 
     System.out.println("eea(1239, 735) = " + apply(BigInteger.valueOf(1239), BigInteger.valueOf(735))); 
    } 

    /* 
    * extended_euclid(d,s) 
      if s = 0 
       than return (d,1,0) 
      (d',s',t') <-- extended_euclid(s, d mod s) 
      return (d',t',s' - (d div s)t') 
    */ 
    public static Triple apply(final BigInteger a, final BigInteger b) { 
     if (b.equals(BigInteger.ZERO)) { 
      return new Triple(a, BigInteger.ONE, BigInteger.ZERO); 
     } else { 
      final Triple extension = apply(b, a.mod(b)); 
      return new Triple(extension.d, extension.t, extension.s.subtract(a.divide(b).multiply(extension.t))); 
     } 
    } 


    private static class Triple { 
     public final BigInteger d; 
     public final BigInteger s; 
     public final BigInteger t; 
     private Triple(final BigInteger d, final BigInteger s, final BigInteger t) { 
      this.d = d; 
      this.s = s; 
      this.t = t; 
     } 
     @Override 
     public String toString() { 
      return "Triple{" + 
        "d=" + d + 
        ", s=" + s + 
        ", t=" + t + 
        '}'; 
     } 
    } 
} 

EEA（240、46）=トリプル{D = 2、S = -9、T = 47}

eea（65,40）=トリプル{d = 5、s = -3、t = 5}

eea（1239,735）=トリプル{d = 21、s = -16、t = 27}

Wikipediaとの応答値を検証しました。