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 11:23:24 -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 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 ?

My prior post was garbled by cut'n paste. Here's the correction.

Yes, if M encrypts to E = M^e mod n, then E^d mod n decrypts it
if (M^e)^d = M (mod n) for all M. Since n is squarefree, this is
true if y(n)|ed-1 [see my first post below, but replace phi(m)
by y(m) = Carmichael lambda, explained in my second post below].

For n = pq the equations below yield y(pq) = lcm(p-1,q-1), so
d correctly descrypts if lcm(p-1, q-1)|ed-1. But this holds true
since by definition of d, (p-1)(q-1)|ed-1, so your observation
follows from: lcm(p-1,q-1)|(p-1)(q-1)|ed-1.

From: Bill Dubuque <wgd@martigny.ai.mit.edu>
Subject: Re: x^3-x always divisible by 6
Date: 1996/11/12

"Christopher Anderson" <cla@netcomuk.co.uk> writes:
>
> While in an interview I was asked why when a value of x is placed into
> x^3-x it is divisible by 6. ... How do I show this using algebra?

More generally, for any squarefree integer m, and any integer x,

      phi(m) + 1
    x = x (mod m) [1]

Recall m is squarefree means that each prime occurs to power at
most one in m, say m = p q ... s, and in this special case the
Euler totient function is simply phi(m) = (p-1) (q-1) ... (s-1).
In your case we have m=6=2*3 so phi(m)=1*2 and x^3=x (mod 6).

To prove [1] above we first prove that it holds (mod p) for
any prime p dividing m: clearly [1] holds if x = 0 (mod p);
otherwise [1] follows from Fermat's Little Theorem (FlT) as
follows:

     phi(m) + 1 p-1 q-1 ... s-1 + 1
   x = x
                     p-1 q-1 ... s-1
                 = (x ) * x
                                          p-1
                 = x since x = 1 (mod p) by FlT

Thus since x^(phi(m)+1)-x is divisible by the distinct primes
p,q,...,s it must be divisible by their product m = p q ... s
(a special case of the Chinese Remainder Theorem).

Note that the above proof fails if m is not squarefree since
x^(p^(n-1)*(p-1)) = 1 (mod p^n) need not hold if p divides x,
e.g. consider x=p=n=2: 2^2 != 1 (mod 4); thus x^3 != x (mod 4).

In general, for any finite group G of size n, all elements x in G
satisfy x^n = 1. Fermat's Little Theorem is a very special case.

These are basic results that can be found in all elementary texts
on algebra, groups, number theory, or finite fields, etc.

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 elts x in group [x coprime to n in Z/(m)]

-Bill Dubuque