mersenneforum.org New way to Find (X^Y) % M
 Register FAQ Search Today's Posts Mark Forums Read

 2004-05-08, 02:52 #1 maheshexp   May 2004 52 Posts New way to Find (X^Y) % M here i had developed a simple algorithm to calculate (X^Y)%M. i works well and faster than any string manipulated operations. //(x^y)%m long r1 = x % m; // loop upto y - 1, for x ^(y-1) for (long i = 0; i < y - 1; i++) { r1 = (r1 * x) % m; } hope this works... mahesh
 2004-05-08, 03:14 #2 ColdFury     Aug 2002 32010 Posts Actually that algorithm is quite trivial and also quite slow. With a Y of 32000, you'd need 32000 multiplications and modular reductions. Using a simple binary exponentiation algorithm, you'd only need on the order of 15.
 2004-05-08, 05:10 #3 Cyclamen Persicum     Mar 2003 1218 Posts I see what you want to say: Instead (x*x*x*x*x*x*...*x) mod y it is possible do not calculate the whole huge product of x, and one should take modulo after every mult, ((((x*x) mod y) *x) mod y) * x) mod y ... That is good guess. But are consequental mults a single way of powering ??? Do you know anything about really fast power algorithm (ordinary or modular) ?
 2004-05-08, 13:55 #4 maheshexp   May 2004 52 Posts what is simple binary exponentiation algorithm, can u explain me that. since i am new to lot of algos...
 2004-05-08, 14:00 #5 maheshexp   May 2004 52 Posts Cyclamen Persicum may i know what is consequental mults a single way of powering ???. since i am new to these type of jargons, and i will try to learn it
 2004-05-08, 14:10 #6 maheshexp   May 2004 318 Posts ColdFury, what u say is right, i am trying to reduce it, but it's very simple rather than multiplying a huge number once , store in a datatype (if it supports ), and dividing it with a number is very huge process. i had benchmarked it with the available resources with java using the builtin functions, i will give u a sample here A 20 bit randomly generated prime number, i have a 2.66GHz system with 640MB ram. it shows the following benchmark ( simple benchmark ) Calculating 65101 ^ 47939 % 47939... ----------------------------- Calculating using My Algorithm... Time Taken using Loop:15 ms Result:17162 ----------------------------- Calculating using System Functions... Time Taken using Java Internals:4906 ms Result:17162
 2004-05-08, 14:12 #7 maheshexp   May 2004 52 Posts sorry it's not 20 bit random, its 16 bit random...since 20 bit random takes more time by system, and i need to waitfor it, but my algorithm takes Time Taken :63 ms Result:670543
 2004-05-08, 14:28 #8 maheshexp   May 2004 52 Posts ColdFury, lets have an ex: 10^20 1: 10 mod 7 = 3 2: 10 mod 7 = 3 3 * 3 = 9 mod 7 = 2 == 100 mod 7 3: 10 mod 7 = 3 2 * 3 = 6 mod 7 = 6 == 1000 mod 7 4: 10 mod 7 = 3 6 * 3 = 18 mod 7 = 4 == 10000 mod 7 and so on....it may look simple for smaller exponents, but when u consider larger exponents , then u will see the difference. another benchmark with a sample number given by me Calculating 12321 ^ 934534 % 456456... ----------------------------- Calculating using My Algorithm... Time Taken using Loop:125 ms Result:258105... my system is calculating still
 2004-05-08, 14:33 #9 maheshexp   May 2004 52 Posts finally my system got done Calculating 10 ^ 934534 % 456456... ----------------------------- Calculating using My Algorithm... Time Taken :78 ms Result:418408 ----------------------------- Calculating using System Functions... Time Taken using Java Internals:96016 ms Result:418408
2004-05-08, 15:52   #10
S80780

Jan 2003
far from M40

53 Posts

Quote:
 Originally Posted by maheshexp what is simple binary exponentiation algorithm, can u explain me that. since i am new to lot of algos...
Binary exponentiation goes like this:

e.g. 5^6%7

1. represent exponent in binary form: 610 = 1102
2. initialize the result as 1. -> 1
3. pass the binary representation of the exponent from left to right.
if the current bit is 1, multiply result by 5. -> 5
reduce result mod 7. -> 5
if you reached the rightmost bit, stop
otherwise square result. -> 25
reduce result mod 7. -> 4
process next bit.

Quote:
 Originally Posted by maheshexp may i know what is consequental mults a single way of powering ???
consequental mults means processing exponentiation by

r = 1;
while y > 0
{
y = y - 1;
r = r*x%m;
}
print r;

this was just a retoric question to let you think of other ways to do modular exponentiation, e.g. binary exponentiation.

Benjamin

 2004-05-08, 18:43 #11 maheshexp   May 2004 52 Posts the binary algorithm is really faster

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Programming 18 2015-07-10 06:08 davar55 Math 2 2010-02-19 16:54 davar55 Puzzles 7 2009-07-02 19:46 davar55 Puzzles 25 2007-07-15 15:56 maheshexp Software 2 2004-05-08 03:16

All times are UTC. The time now is 22:38.

Wed Dec 1 22:38:39 UTC 2021 up 131 days, 17:07, 1 user, load averages: 1.19, 1.31, 1.38