I'm trying to implement the EEA. I found this pattern which I use also.
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)
And my code looks like this:
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())));
}
}
I'm not quite sure if my code is correct. I looked up many pages like twenty or so but I still don't get it. I'm mentally stuck. Thanks.
It looks like you got the operations in the final return out of order. You also implemented the third value of Triple incorrectly. Here is my implementation. (I also used BigInteger's helper constants/methods + renamed variables for clarity.)
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}