Euler's totient function
Euler’s totient function maps a positive integer to the number of positive integers less than it that are coprime to it.
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.
- How it is used
- Supports RSA key generation by deriving the private exponent from the public exponent and the hidden prime factors.
- 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 you can do after
- Apply it via RSA key generation by calculating φ(n), checking coprimality, and deriving the private exponent.
Read how Hacking Cryptography explains Euler's totient function →
Real-World Cryptography
Euler's totient function counts the positive integers up to a given integer that are coprime to it.
- How it is used
- Connects RSA’s hidden group order to the computation of its private exponent.
- 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 you can do after
- Evaluate/understand how ϕ(N) determines RSA’s group order and supports private-exponent derivation.
Read how Real-World Cryptography explains Euler's totient function →
Related concepts
- multiplicative groupmeasures · A multiplicative group is a group whose operation is written as multiplication, with an identity element and an inverse for every element.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.