Re: A question about modular exponentiation
From: Bill Dubuque (firstname.lastname@example.org)
From: Bill Dubuque <email@example.com> Date: 24 Apr 2003 04:08:48 -0400
Paul Schlyter <firstname.lastname@example.org> wrote:
> In RSA, keys are usually generated in this way:
> 1. Generate two primes, p and q, and compute the modulus n = pq
> 2. Choose a public exponent e, a common choice is e = 65537
> 3. Compute the private exponent d from:
> d = 1/e mod (p-1)(q-1)
> One can also compute the private exponent in a slightly different way:
> d' = 1/e mod LCM(p-1,q-1)
> [...] my question is: when d and d' are different, does always both
> of them work with the one and same public exponent e and modulus n ?
Yes, if M encrypts to E = M^e mod n, then E^d mod n decrypts it
iff (M^e)^d = M (mod n), so we need M^ed = M (mod n) for all M
[necessarily coprime to n]. This identity holds true iff ed is
a multiple of y(n) = Carmichael lambda function of n [see below].
For n = pq the equations below yield y(pq) = lcm(p-1,q-1) = d'
Thus d = (p-1)(q-1), being a multiple of d', also decrypts M.
From: Bill Dubuque <email@example.com>
Date: 30 May 2002 02:57:46 -0400
Subject: Re: elementary number theory question
Chris Nolen <firstname.lastname@example.org> wrote:
> In my number theory homework I showed that if n is an integer
> not divisible by 2 or 3 then n^2 + 23 must be divisible by 24.
> Is there a general theory that relates to this?
You showed that a^2 = 1 (mod 24) if (a,24) = 1. More generally,
k = y(m) => a^k = 1 (mod m) if (a, m) = 1
where y(m) is the Carmichael lambda function, defined as is the
Euler phi function on prime powers, but combined via lcm vs. times:
y(2 ) = 2 for e>2; y(4) = 2, y(2) = y(1) = 1
y(p ) = p (p-1) for odd prime p
i j i j
y(p q...) = lcm( y(p ), y(q ), ... )
In your case y(24) = y(2^3*3) = lcm(2,2) = 2, as you showed,
and it's easy to see that 24 is the largest m with y(m) = 2.
In group theoretic language one says the y(m) is the exponent
of the unit group of Z/(m), i.e. the smallest k such that
x^k = 1 for all x in the group [ x coprime to n in Z/(m) ]