f : x -> pow(x, pubkey) mod m
g : x -> pow(x, privkey) mod m
being inverses of each other was a big breakthrough when it was discovered. The article implies, but does not directly state, that this "big breakthrough" was part of what separated the "classical" era of cryptography (pre-1977 as defined by the article) from the "modern" era (post-1977).
The "big breakthrough" result was actually proven by Euler hundreds of years ago! [1] The innovation of RSA was building a working public-key cryptosystem around Euler's result, not the result itself.
Fermat's little theorem is Euler's theorem in the special case that m is prime. The condition on Euler's theorem is that x and m must be relatively prime... which is certainly true if m is prime.
Comments
The article says that the two functions,
being inverses of each other was a big breakthrough when it was discovered. The article implies, but does not directly state, that this "big breakthrough" was part of what separated the "classical" era of cryptography (pre-1977 as defined by the article) from the "modern" era (post-1977).The "big breakthrough" result was actually proven by Euler hundreds of years ago! [1] The innovation of RSA was building a working public-key cryptosystem around Euler's result, not the result itself.
[1] http://en.wikipedia.org/wiki/Euler%27s_theorem
I've usually heard it referred to as http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
Fermat's little theorem is Euler's theorem in the special case that m is prime. The condition on Euler's theorem is that x and m must be relatively prime... which is certainly true if m is prime.