扩展欧几里德算法 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())));
    }
}

我不太确定我的代码是否正确。我查了很多页，大约二十页，但我还是不明白。我精神上被困住了。谢谢

Answer 1

看起来你在最后的 return 中的操作是乱序的。您还错误地实现了 Triple 的第三个值。这是我的实现。（为了清楚起见，我还使用了 BigInteger 的助手 constants/methods + 重命名的变量。）

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) = Triple{d=2, s=-9, t=47}

eea(65, 40) = Triple{d=5, s=-3, t=5}

eea(1239, 735) = Triple{d=21, s=-16, t=27}

我验证了来自 Wikipedia and here 的响应值。

扩展欧几里德算法 JAVA RSA

Extended Euclidean algorithm JAVA RSA

java

algorithm

modular-arithmetic