Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/