liveBook · Manning

Euler's theorem

As explained in Real-World Cryptography

Euler's theorem states that an integer coprime to a modulus raised to the order of the corresponding multiplicative group is congruent to one modulo that modulus.

Euler's theorem explains why exponentiation can eventually return a number to its original value. If m is coprime with p, then m raised to the group's order is congruent to 1 modulo p. section 6.3.1

Its role in textbook RSA follows a short chain:

  • Use m^order ≡ 1 mod p for a message m coprime with p. section 6.3.1
  • Choose exponents e and d so that e × d ≡ 1 mod order. section 6.3.1
  • Recover the message because raising ciphertext to d produces m^(e×d) ≡ m. section 6.3.1
  • For an RSA modulus N = p × q, use Euler's totient function to count numbers coprime with N and conceal the group's order. section 6.3.1

A cyclic subgroup

With integers modulo 5, choose 2 as a generator and repeatedly exponentiate it. After enough powers, the sequence returns to 2, illustrating the cyclic behavior used to reverse exponentiation.

How Real-World Cryptography covers it

How deep it goes
Derives the modular-inverse equation from the theorem but avoids a formal proof and implementation detail.
Examples
Uses integers modulo 5 and the message 2 to illustrate cyclic exponentiation and message recovery.
What it assumes
Assumes modular arithmetic while defining coprimality, group order, and modular inverses in context.
What you can do after
Evaluate how Euler's theorem supports RSA decryption and private-exponent construction.
How it connects
Connects modular arithmetic, multiplicative groups, modular inverses, Euler's totient function, and RSA.
Cover of Real-World Cryptography
liveBookmanning.com
Read Real-World Cryptography on liveBook Get the book at manning.com

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.