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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.