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

### The Square and Multiply Method

```
Date: 08/31/98 at 08:05:37
From: krishnan Ravi
Subject: Logarithms

I am trying to solve an encryption problem in which I need to solve the
following math function. The equation is this:

33815^(81599) (mod 154381)

I would appreciate it if you could give me some advice on how to solve
this problem. I have tried using logarithms on a calculator, but the
number is too large.

Thanks,
Ravi
```

```
Date: 08/31/98 at 11:01:47
From: Doctor Rob
Subject: Re: Logarithms

The way to compute the modular value of this exponential is as follows.

Start with the exponent 81599. Write down a column consisting of this
number in the first row. In each following row, if the number above it
is odd, write down the number less one, and if the number is even,
write down half the number:

81599
81598
40799
40798
20399
20398
10199
10198
5099
5098
2549
2548
1274
637
636
318
159
158
79
78
39
38
19
18
9
8
4
2
1

You are going to use these numbers from the bottom up to compute 33815
raised to the power 81599 mod 154381, by computing 33815^i (mod 154381)
for each i in this column. The bottom one is easy: 33815^1 = 33815.
Write this in a second column to the right of the "1" in the first
column.

For each row above the last one, if the number in the first column is
even, square the number in the second column of the row below and
reduce the result modulo 154381. In this case, 33815^2 = 1143454225,
which is congruent to 108539 (mod 154381). This goes in the second
column, next to last row. Above that goes 108539^2 = 54792 (mod
154381). Above that goes 54792^2 = 70338 (mod 154381). Now we come to
a row with a number in the first column which is odd. Now instead of
squaring, multiply 33815 times the number below, and reduce modulo
154381.  In this case, 70338*33815 = 85784 (mod 154381).

Continue this process until you have filled in the first row.

This method is called the square-and-multiply method. It is related to
the binary expansion of the exponent 81599 base 10 = 10011111010111111
base 2. If you look at the binary bits from the left, you will find
the numbers 1, 2, 4, 9, 19, 39, 79, 159, and so on, which appear in
the first column of the above constructed table.

Your numbers should never be larger than 154830^2 = 23833184400, so
you won't have problems with overflow if you can handle numbers as
large as that, which contains 35 binary bits and 11 decimal digits.

- Doctor Rob, The Math Forum
Check out our web site 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