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

Name: Euler Totient for RSA
Availability: InStock
Author: Nham Vu

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

The extended Euclidean algorithm tracks coefficients s and t such that a·s + b·t = gcd(a,b) at every row. When the remainder hits 0, gcd is found. The final t (adjusted to be positive mod φ(n)) is your private exponent d.

Copied!

Summary