6

Apparently an alternative method (to just using the extended Euclidean algorithm) of obtaining the exponent for deciphering is to do d = e**(phi(phi(n))-1) mod(phi(n)). Why does this work?

1 Answer 1

16

The general requirement for the RSA operation to function properly is that e*d = 1 mod X, where X is typically (p-1)*(q-1).

In this case, X is phi(n), e is e, and d is e^[phi(phi(n))-1] = e^[phi(X)-1].

Notice that e*d mod X is e*e^[phi(X)-1] mod X = e^phi(X) mod X.

Euler's Theorem states that a^phi(X) = 1 mod X, for any a which is relatively prime to X, thus the requirement holds.

1
  • All true except that X is not p*q. X is (p-1)*(q-1) where n=pq and p and q are both prime.
    – Jason S
    Jun 11, 2011 at 15:28

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.