liveBook · Manning

Euler's totient function

As explained in Hacking Cryptography

Euler's totient function maps a positive integer to the number of positive integers smaller than it that are relatively prime to it.

Euler's totient function, written φ(n), counts the positive integers smaller than n whose greatest common divisor with n is 1. In RSA, when n is the product of two primes p and q, φ(n) = (p − 1)(q − 1). section 8.3.2

RSA uses the totient during key generation:

  • Generate two secret random primes, p and q, and publish their product n = pq. section 8.3.2
  • Compute φ(n) = (p − 1)(q − 1); this value remains secret because it depends on the hidden factorization of n. section 8.3.2
  • Choose a public exponent e relatively prime to φ(n), then calculate the private exponent d as e's multiplicative inverse modulo φ(n). section 8.3.2
  • Use the extended Euclidean algorithm to compute d efficiently from e and φ(n). section 8.3.2

The function is therefore a bridge between RSA's public modulus and private exponent: knowing φ(n) makes the modular inverse calculation straightforward, while recovering it from n requires the secret prime factors. A public exponent of e = 3 is valid when it is coprime to φ(n); the exponent alone does not create a vulnerability. section 8.3.2 section 9.6.2

RSA key generation with e = 3

A Go implementation generates random primes p and q, computes n, calculates φ(n) with (p − 1)(q − 1), selects e = 3, and obtains d with ModInverse(e, φ). It retries when the inverse does not exist. The resulting public key contains (n, e), while the private key contains d. section 9.6.2

How Hacking Cryptography covers it

How deep it goes
Defines coprimality, gives the two-prime formula, and traces exponent selection and inversion, but does not derive totient formulas generally.
Examples
Uses two-prime RSA key generation, public exponent e = 3, and a Go implementation that calls ModInverse.
What it assumes
Assumes familiarity with prime numbers, modular arithmetic, and greatest common divisors while defining relative primality from zero.
What you can do after
Apply it via RSA key generation by calculating φ(n), checking coprimality, and deriving the private exponent.
How it connects
Connects Euler's totient function to RSA, integer factorization, greatest common divisor, modular inverse, and the extended Euclidean algorithm.
Cover of Hacking Cryptography
liveBookmanning.com
Read Hacking 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 Hacking Cryptography. The section links point to the parts of the book it draws on.