I'm doing some self-study in cryptography and have come across something that I don't understand. Hoping somebody can help me with the gap in my knowledge.
I'm trying to follow an algorithm to compute exponentiation using Euler (really Fermat), and am stuck on some modular arithmetic. The problem before me is to compute
The example that I am studying right now says that this is equal to: , which I can see is an application of Fermat's theorem (since 23 is prime). The next step is what I don't understand. They go on to apply Fermat again, saying that:
I understand why they switched to mod 10 (there are 10 elements in the set phi(22)). What I don't understand are the following:
1) How can they drop the base 2?
2) Where did the mod 23 go? (these might be the same property)
Clearly, there is some property of modular arithmetic that I don't understand in applying these theorems. Can anyone explain this to me?