Euler's Totient Function φ(n)

φ(n) = (p-1)(q-1)

φ(n)

Totient Function

Counts coprimes ≤ n

p, q

Distinct Primes

RSA key factors

(p-1)(q-1)

Multiplicative Property

For coprime factors

(p - 1)

32,316

First prime - 1

(q - 1)

40,008

Second prime - 1

φ(n)

1,292,854,328

KEEP SECRET

MATHEMATICAL FOUNDATION

Definition: φ(n) = |{k ∈ ℕ : 1 ≤ k ≤ n, gcd(k,n) = 1}|

For prime p: φ(p) = p-1
For coprime m,n: φ(mn) = φ(m)φ(n)
                

RSA Usage: Enables private key calculation

Time: O(1) if factors known, O(√n) general case

Knowledge of φ(n) ≡ factorization of n

MULTIPLICATIVE PROPERTY

Given: n = pq, where p,q are distinct primes

gcd(p,q) = 1 (coprimality of distinct primes)

φ(pq) = φ(p)·φ(q) by multiplicative property

φ(p) = p-1, φ(q) = q-1 for primes

∴ φ(n) = (p-1)(q-1) ∎

RSA Key Gen: d ≡ e⁻¹ (mod φ(n))

PRIME CASE

For prime p, all integers 1 to p-1 are coprime to p

φ(p) = p-1
gcd(k,p) = 1 ∀k ∈ {1,2,...,p-1}
                    

φ(7) = 6

φ(13) = 12

SEMI-PRIME

For n=pq, count non-coprimes and subtract from total

Non-coprimes: multiples of p or q
Count = (q-1) + (p-1) = p+q-2
φ(pq) = pq - (p+q-2) + 1 = (p-1)(q-1)
                    

RSA ALGORITHM

Private key derivation steps:

Choose p,q prime
n = pq, φ(n) = (p-1)(q-1)
Pick e: gcd(e,φ(n)) = 1
Find d: ed ≡ 1 (mod φ(n))
Public: (n,e), Private: (n,d)
                    