Editing Euler's totient function (section)

==Euler's theorem==

{{main article|Euler's theorem}}

This states that if {{mvar|a}} and {{mvar|n}} are [[relatively prime]] then

:<math> a^{\varphi(n)} \equiv 1\mod n.</math>

The special case where {{mvar|n}} is prime is known as [[Fermat's little theorem]].

This follows from [[Lagrange's theorem (group theory)|Lagrange's theorem]] and the fact that {{math|''φ''(''n'')}} is the [[order (group theory)|order]] of the [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{mvar|n}}]].

The [[RSA (algorithm)|RSA cryptosystem]] is based on this theorem: it implies that the [[inverse function|inverse]] of the function {{math|''a'' ↦ ''a<sup>e</sup>'' mod ''n''}}, where {{mvar|e}} is the (public) encryption exponent, is the function {{math|''b'' ↦ ''b<sup>d</sup>'' mod ''n''}}, where {{mvar|d}}, the (private) decryption exponent, is the [[multiplicative inverse]] of {{mvar|e}} modulo {{math|''φ''(''n'')}}. The difficulty of computing {{math|''φ''(''n'')}} without knowing the factorization of {{mvar|n}} is thus the difficulty of computing {{mvar|d}}: this is known as the [[RSA problem]] which can be solved by factoring {{mvar|n}}. The owner of the private key knows the factorization, since an RSA private key is constructed by choosing {{mvar|n}} as the product of two (randomly chosen) large primes {{mvar|p}} and {{mvar|q}}. Only {{mvar|n}} is publicly disclosed, and given the [[Integer factorization|difficulty to factor large numbers]] we have the guarantee that no one else knows the factorization.