how to hand calculate RSA decryption exponent (using small numbers)

Question

This is a simple exercise to help my personal understanding of RSA. I'm not trying to do anything that will have real world security.

I want to compute the RSA decryption exponent d, where d = e−1 mod φ(n).

I would prefer to make the calculation using a method similar to this:

int d = (k * (p - 1) * (q - 1) + 1) / e;

where e is the RSA encryption exponent and p and q are randomly generated primes. I will use small primes (e.g., 7, 13) and I will also pick e to be something small like 5.

Why do I want to do it similar to that method? Although I am using the Java language, I am looking for a simple "hand calculation" method. In particular I do not want to use something similar to the following method, which is what I find recommended on all the programming-related forums:

BigInteger d = e.modInverse(totient);

I am trying to avoid calling any external functions. To me modInverse() is a "black box" and I'm trying to avoid those so that I can increase my understanding (although I'm working at a simple level of understanding).

Once I have picked e, p and q how do I find k? Once I have k, of course, finding d is trivial in my example.

The value of k should be an integer (it must result in an integer value of d, the decryption exponent).

Example:

With p=13,q=7,e=5 then k = 2 (and therefore, d = 29).

I need to find integer k given any small integer e, and small primes p and q. (Also, I would prefer not to iterate, if possible.)

Please keep the answers simple because I don't have any math background. Thanks.

EDIT: claried based on comments.

Answer 1

For such small values, of course iteration is the simplest method. But for larger parameters, the standard procedure (probably used by Java's modInverse method) is the extended Euclidean algorithm for computing modular inverses. This is not especially complicated, but neither is it trivial to program. Have fun!