Computing a^((N-1)/2) mod N

Date: 12/07/98 at 19:30:32
From: Dana Perriello
Subject: How is a^((N-1)/2) mod N done?

The Proth's theorem states that N (which is k*2^n+1) is prime if there 
is an integer a where a^((n-1)/2)=-1(mod N). I want to write a program 
using that formula. 

Is there a shortcut for doing a^((n-1)/2) mod N?

Date: 12/08/98 at 20:36:01
From: Doctor Kate
Subject: Re: How is a^((N-1)/2) mod N done?

Dana:

I'm glad to see you're exploring so much. There are a few shortcuts for 
trying to do large powers in mods. The first uses the nice property 
that

   if  a = b(mod n)  and  c = d(mod n),  then  ac = bd(mod n).

You can work this out in the integers by using the definition of the 
modulus:

   a = b + nk  and  c = d + nl  for some integers we'll call k and l.

So then 

   ac = (b + nk)(d + nl) 
      = bd + nkd + nlb + n^2kl 
      = bd + n(kd + lb + nkl)

which means that  ac = bd(mod n)  since kd + lb + nkl is just some 
integer.

For the rest of my letter, I'm going to write 

   "reduced form of a mod n" 

to mean the remainder of a when divided by n.  We call it "reduced" 
because it's pretty small.

Now what we know, in essence, is that we can get the same answer by 
reducing things before or after multiplying them together, when we're 
working in some mod n. Since multiplying smaller things is easier, 
reducing before we multiply will save us work (and stop the computer 
from choking on huge numbers).

So how can we use this for a shortcut?  Well, if the exponent is 
really large, we can "split it up" because

   a^(p+q) = (a^p)(a^q)

So if we can figure out a^p and a^q, we can reduce them before we 
multiply them together to get a^(p+q).  So we never have to deal with 
a number as big as a^(p+q) at all.

So you might suggest then that to find a^m, you could simply multiply 
a by itself, reduce, then multiply again by a, then reduce, and so on. 
 
However, this is still a lot of work.  To save work, there's a really 
clever trick:

Suppose we want to compute a^m, where m is some power of 2. Say

   a^(2^k), for some integer k.

So to begin, we multiply a by a, and reduce. We now know the reduced 
form of a^2. So instead of multiplying by a and reducing twice more, 
why don't we just multiply by a^2 instead? This will save a step. So 
then we find (a^2)*(a^2). When we reduce this, we have the reduced form 
of a^4, so we can save three steps. This is a really useful trick in 
general. 

So you'll have a nice reduced form of a^(2^k) in k steps (try it!) 
instead of 2^k steps. That's much quicker!

But what if m isn't a power of 2? Well, then we can try to write it 
as a sum of powers of 2. For instance, suppose you have a^21 (mod n). 
 
Then, 21 = 16 + 4 + 1

So we can write a^(21) = a^(16+4+1) = a^16 * a^4 * a

So we need only figure out reduced forms for a^16, a^4 and a (well, we 
already have one for a). It will take four steps to find a^16, and 
we'll find a^4 on the way. So let's do a concrete example.

Take  3^21 (mod 7)

We find 3^2: 3^2 = 9 = 2(mod 7), so 2 is the reduced form of 3^2.

We find 3^4: 3^4 = (3^2)^2 = 2^2 = 4(mod 7), so 4 is the reduced form 
of 3^4.

We find 3^8: 3^8 = (3^4)^2 = 4^2 = 16 = 2(mod 7), so 2 is the reduced 
form of 3^8.

We find 3^16: 3^16 = (3^8)^2 = 2^2 = 4(mod 7), so 4 is the reduced 
form of 3^4.

So now we have 3^21 = 3^16 * 3^4 * 3 = 4 * 4 * 3 = 48 = 6 (mod 7).

It's so easy now that we can do it by hand, without the computer!

This is a bit tricky to program on a computer, but it is the most 
useful shortcut we have available for this sort of thing. Don't 
hesitate to write us again with questions, and good luck!

- Doctor Kate, The Math Forum
  http://mathforum.org/dr.math/   

Date: 03/23/2001 at 02:46:52
From: Mike Li
Subject: The mistake Dr. Kate made about ac=bd(mod n)

Hi -

A few days ago I asked a question about modulus, but then I was lucky 
enough to find Dr. Kate's post in the archive section. It was a great 
explanation, it helped me to solve the question I asked. However, I 
believe there was a mistake in the reply: "a = b(mod n) and c = d(mod n), 
then  ac = bd(mod n)". This is not right.

  Dr. Kate was right about:
   ac = (b + nk)(d + nl) 
      = bd + nkd + nlb + n^2kl 
      = bd + n(kd + lb + nkl)

But then (kd + lb + nkl) might not be the appropriate value to give 
us the right remainder; in other words, ac still contains extra 
multiples of n. 

To get rid of them, we use ac(mod n); therefore the right equation 
should be: 

a = b(mod n) and c = d(mod n), then ac(mod n)= bd(mod n)

which can be also expressed as a(mod n)^e(mod n)=a^e(mod n), the same 
equation as in my previous question.

This site is great - I love it!

Date: 03/23/2001 at 09:08:13
From: Doctor Peterson
Subject: Re: The mistake Dr. Kate made about ac=bd(mod n)

Hi, Mike.

It appears you have a slight misunderstanding about the meaning of 
(mod n) as used here - an error that is probably due to the misuse of 
the term "mod" in the computer programming world, since I see that your 
previous question dealt with programming.

In math, (mod n) is not an operator or modifier of a number (giving its 
remainder), but a modifier of the whole equation, or rather of the 
"equals" (congruence) symbol, which tells us in what sense two numbers 
are "equal." When we write

    a = b (mod n)

(properly using the triple "=" rather than the ordinary "two lines" 
symbol we have to use here), it means that a and b are "congruent 
modulo n" - that is, that they differ by a multiple of n. Nothing is 
said about the size of a or b.

(It's worth noting that "modulo n" is actually Latin for "with respect 
to the modulus, or divisor, n." So "mod n" is really an adverbial phrase 
modifying the verb "is congruent." And, contrary to common usage, the 
"modulus" here is n, not a.)

In computer languages, "mod" (or a symbol such as %) is used as a 
remainder operator, so that "b mod n" means "the remainder when you 
divide b by n." Since this function must give a single number as its 
value, this is taken to be the principal value of the remainder, 
0 <= b mod n < n. 

(There are conflicting opinions as to what it should mean when b 
and/or n are negative, sometimes leading to a need for two different 
operators or functions, MOD and REM; but I won't go into that issue.) 

In that case, if I said

   a = b mod n

I would be making a statement about the size of a (that it is less than 
n), not only about the relation between a and b. In these terms, if I 
wanted to express my congruence above, I could say

    a mod n = b mod n

since two numbers are congruent if and only if they have the same 
remainder. That appears to be what you are saying; but what you mean is 
exactly the same as what Dr. Kate said, using proper mathematical 
terminology.

Here are some pages I found (by doing a search for "congruent remainder 
modulo") that may help clarify some of these ideas:

Congruences (from Beachy/Blair, Abstract Algebra)
http://www.math.niu.edu/~beachy/abstract_algebra/study_guide/13.html   

Introduction to Modular Arithmetic - Trailpost 3
http://www.cs.usask.ca/resources/tutorials/csconcepts/numbertheory/tutorial/trail/tp03.html   

Congruences - Number Theory and Cryptography (Booth) (download PDF file)
http://www.ma.umist.ac.uk/rb/teaching/117/part4.pdf   

You can find a lot more, and probably better, discussions than these if 
you look around; these are just the first few I found.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/