What is Euler's totient function?

φ(n) counts the integers from 1 to n that are coprime to n. For a product of two distinct primes n = p × q, it simplifies to (p-1) × (q-1) — the number of integers less than n that share no common factor with n.

Why must e and φ(n) be coprime?

For the private exponent d to exist as a modular inverse of e, the equation e × d ≡ 1 (mod φ(n)) must have a solution. This is only possible when gcd(e, φ(n)) = 1, guaranteeing a unique d.

d is the modular inverse of e modulo φ(n), found using the extended Euclidean algorithm. It repeatedly applies the relation gcd(a, b) = gcd(b, a mod b) while tracking coefficients, then back-substitutes to express 1 as a linear combination of e and φ(n).

Why must p and q be prime?

RSA security depends on the difficulty of factoring n. If p or q is composite, factoring becomes easier and the totient formula φ(n) = (p-1)(q-1) no longer holds, producing incorrect keys.

What are the public and private keys?

The public key is the pair (n, e) — shared openly. The private key is the pair (n, d) — kept secret. Encryption computes c = m^e mod n; decryption computes m = c^d mod n.

Is this tool safe for real RSA keys?

No. Real RSA uses primes of 2048 bits or more. This tool is for education and uses small numbers so you can verify the arithmetic by hand. Never use small primes for actual encryption.

Euler Totient for RSA

Enter two primes p and q to compute φ(n), pick a public exponent e, and see the full RSA key generation process step by step.

Inputs

Prime p

Prime q

Public exponent e (optional)

Must satisfy 1 < e < φ(n) and gcd(e, φ(n)) = 1

Quick examples

RSA Key Components

Enter primes above and click Compute.

Totient Derivation

—

Extended Euclidean Algorithm — finding d

—

Step	a	b	q = ⌊a/b⌋	r = a mod b	s	t
Compute to see steps.

What the columns mean

At each displayed row, s and t are the coefficients of the current b: φ(n)·s + e·t = b. When the remainder reaches 0, the last nonzero row gives the Bézout coefficient for e; reducing it modulo φ(n) gives the private exponent d.

Copied!

Summary

This tool computes Euler's totient function φ(n) = (p-1)(q-1) for two primes p and q, then derives a complete RSA key pair. It finds a valid public exponent e, computes the private exponent d using the extended Euclidean algorithm, and shows every intermediate step so you can follow the math used in real RSA implementations.

How it works

Enter two distinct prime numbers p and q.
The tool computes the RSA modulus n = p × q.
Euler's totient is calculated as φ(n) = (p-1) × (q-1).
A valid public exponent e is chosen: 1 < e < φ(n) with gcd(e, φ(n)) = 1.
The private exponent d = e⁻¹ mod φ(n) is found via the extended Euclidean algorithm.
The step-by-step table shows every division, quotient, and back-substitution used to find d.

Use cases

Learn RSA key generation for a cryptography course.
Verify hand-computed RSA homework answers.
Understand why the extended Euclidean algorithm is used to find d.
Debug a custom RSA implementation by checking intermediate values.
Explore how small prime choices affect key size and security.
Visualize the relationship between p, q, n, φ(n), e, and d.

Frequently Asked Questions

Last updated: 2026-10-05 · Reviewed by Nham Vu