After finding the values of p and q, we can calculate d which is the modular multiplicative
Fantastic news! We've Found the answer you've been seeking!
Question:
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)
Related Book For
Mathematical Interest Theory
ISBN: 9781470465681
3rd Edition
Authors: Leslie Jane, James Daniel, Federer Vaaler
Posted Date: