# Re: A question about modular exponentiation

From: Bill Dubuque (wgd@nestle.ai.mit.edu)
Date: 04/24/03

```From: Bill Dubuque <wgd@nestle.ai.mit.edu>
Date: 24 Apr 2003 04:08:48 -0400

```

Paul Schlyter <pausch@saaf.se> 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 <wgd@nestle.ai.mit.edu>
Date: 30 May 2002 02:57:46 -0400
Subject: Re: elementary number theory question

Chris Nolen <cmnolen@ualr.edu> 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:

e e-2
y(2 ) = 2 for e>2; y(4) = 2, y(2) = y(1) = 1

e e-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) ]

-Bill Dubuque