# Re: A question about modular exponentiation

**From:** Bill Dubuque (*wgd@nestle.ai.mit.edu*)

**Date:** 04/24/03

**Next message:**Bill Unruh: "Re: "smart" bruteforce method for RSA ?"**Previous message:**Mok-Kong Shen: "Re: Cohen's paper on byte order"**In reply to:**Bill Dubuque: "Re: A question about modular exponentiation"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**Bill Unruh: "Re: "smart" bruteforce method for RSA ?"**Previous message:**Mok-Kong Shen: "Re: Cohen's paper on byte order"**In reply to:**Bill Dubuque: "Re: A question about modular exponentiation"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]