Extended Euclidean algorithm JAVA RSA

Question

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.

FYI: there are constants BigInteger.ZERO and BigInteger.ONE. — Maurice Perry
– Maurice Perry, Commented Jul 14, 2023 at 12:02

Kenny Cason · Accepted Answer · 2016-05-27 06:47:31Z

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}

I validated the response values from Wikipedia and here.

Collectives™ on Stack Overflow

Extended Euclidean algorithm JAVA RSA

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related