Hello,
I recently solved problem RSA. But one detail confused me. One of the needs of the problem is to find the modular inverse of one number A module MOD. I always computed this operation with Euler's theorem stated here Theorem. But in this problem, surprisingly, it doesn't work, and I had to compute this modular inverse though the Extended GCD algorithm. Is there any cases which Euler's theorem doesn't work ?
Euler's theorem Code (I've used this code in dozens of problems without trouble)
Extended GCD Code
m - 2 = φ(m) - 1 when m is prime and in this problem it is definitely composite.
Euler's theorem works fine for prime numbers, but afaik Mod in rsa encrypting is not a prime one.
Actually it works for composite numbers too. The only thing you must keep in mind — a and m must be coprime.
The problem here is in calculation of Euler's function of a composite number.
So, for non coprime numbers, only the extended gcd algorithm works ?
For non-coprime integers there is no modular inverse number.
But the problem states that A and B are coprime, then, my curiosity is why I have different results using Fermat's Little Theorem and Extended GCD algorithm ?
One more time: because Fermat's Little Theorem works only for prime modulo. For composite modulo use the general case — the Euler's theorem.
I believe you say about Fermat's little theorem which is particular case of Euler's theorem.