Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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.

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

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.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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search