chiark / gitweb /
 author Mark Wooding Thu, 25 Jul 2013 17:30:45 +0000 (18:30 +0100) committer Ian Jackson Thu, 25 Jul 2013 17:30:45 +0000 (18:30 +0100) commit 104e8e74fd858a4efff3d8e186406adc431465fa tree f3aaf0dfe16497d890006b6783aa7937cf5c1965 tree | snapshot parent e8a0782f42c256c06905e0006ba4473b08ba3bf7 commit | diff
rsa.c: Fix incorrect commentary.

The Euler function phi(n) is defined to be

phi(n) = #{ 1 < i < n | gcd(i, n) = 1 }

the number of natural numbers less than n and prime to it; equivalently,
it's the size of the multiplicative group (Z/nZ)^*.

If n = p q is the product of two primes then phi(n) = (p - 1)(q - 1).
But phi(n) is not (if n is composite) the exponent of (Z/nZ)^*.  It's
certainly true that

a^{phi(n)} = 1

for all a in (Z/nZ)^*; but the exponent of a group G is the /smallest/
positive integer e such that

a^e == 1

for all a in G.  This quantity is denoted lambda(n); in our simple case
where n = p q is the product of two primes it's true that

lambda(n) = lcm(p - 1, q - 1)

Since p and q are large primes, both p - 1 and q - 1 are even, so
lambda(n) is at least a factor of 2 smaller than phi(n).

In fact, lambda(2) = 1, lambda(2^f) = 2^{f-2} for f >= 1, and
lambda(p^f) = p^{f-1} (p - 1) for prime p > 2; and, in general, if n =
p_1^{f_1} ... p_m^{f_m} is the prime factorization of n then

lambda(n) = lcm(lambda(p_1^{f_1}), ... lambda(p_m^{f_m}))

Signed-off-by: Mark Wooding <mdw@distorted.org.uk>
 rsa.c diff | blob | history