After finding the values of p and q, we can calculate d which is the modular multiplicative inverse of e. The Extended Euclidean Algorithm can be used for the calculation. How to transfer it as a Java program for this algorithm based on the pseudocode as shown below:

/* Pseudocode */ Specification: Input: public exponent (e), modulus (phi_n) Output: modular multiplicative inverse of e BEGIN 1. (A1, A2, A3) = (1, 0, phi_n); (B1, B2, B3) = (0, 1, e); 2. if B3 = 0 return A3 which is GCD(phi_n, e) and there is no inverse; 3. if B3 = 1 return B3 which is GCD(phi_n, e) and B2 which is the inverse of e; 4. Q = A3 div B3; 5. (T1, T2, T3) = (A1 - Q * B1, A2 - Q * B2, A3 - Q * B3); 6. (A1, A2, A3) = (B1, B2, B3); 7. (B1, B2, B3) = (T1, T2, T3); 8. goto 2; END

e.g)

n=12,527,891 e=823

p=3761 q=3331

phi(n) = (p-1)(q-1)

Q: What is d? (output)