Reformulate an equation to me faster in java

Question

I'm working on encryption, and for the private key exponent d, you need to multiply d by e and take the mod of another number, and have the remainder be 1. the function i have already is this:

private void genD() {
        d = e / 2;
        // solve for d given d*e = 1 (mod eN)
        while ((d * e) % eN != 1) {
            d++;
        }
}

what i have now is obviously a brute way of doing things, going through every single number until one works. I know the equation does its job, plugging in the numbers using the working example found here, but it is VERY VERY VERY slow with using for the numbers i'm generating. Logically I feel there is a way to get this done MUCH faster, but I'm unable to think of how?

Any help is appreciated! Thanks in advance :)

Answer 1

There are fast multiplicative inverse algorithms which aren't terribly difficult, but there's also one built into Java:

 BigInteger.valueOf(e).modInverse(BigInteger.valueOf(eN)).intValue();

The most popular algorithm to compute the multiplicative inverse mod another number is http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers .