liveBook · Manning

Euler's totient function

As explained in Real-World Cryptography

Euler's totient function counts the positive integers up to a given integer that are coprime to it.

Euler’s totient function, written ϕ(N), counts the positive integers that are coprime with N. Two numbers are coprime when their only shared positive divisor is 1. section 6.3.1

In RSA, the function supplies the order of the multiplicative group modulo the public modulus:

  • For N = p × q, where p and q are secret large primes, ϕ(N) = (p − 1) × (q − 1). section 6.3.1
  • That order helps derive the private exponent d as the inverse of the public exponent e modulo ϕ(N). section 6.3.1
  • Calculating ϕ(N) is difficult without knowing how N factors into p and q, supporting RSA’s reliance on the factorization problem. section 6.3.1

A small coprimality check

The numbers 5 and 6 are coprime because only 1 divides both. The numbers 10 and 15 are not, because 1 and 5 divide both. section 6.3.1

How Real-World Cryptography covers it

How deep it goes
Defines coprimality, gives the RSA product formula, and stops short of a formal proof.
Examples
Uses 5 and 6, 10 and 15, and an RSA modulus N = p × q.
What it assumes
Introduces coprimality through divisor examples while assuming familiarity with primes, modular arithmetic, and RSA notation.
What you can do after
Evaluate/understand how ϕ(N) determines RSA’s group order and supports private-exponent derivation.
How it connects
Links modular arithmetic, multiplicative groups, RSA, modular inverses, and the factorization problem.
Cover of Real-World Cryptography
liveBookmanning.com
Read Real-World Cryptography on liveBook Get the book at manning.com

Also explained in

Compare how 2 books explain Euler's totient function →

Related concepts

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.