Re: Big Mod algorithm

[Josef Spillner <dr_maux@users.sourceforge.net>]

On Sunday 17 August 2003 19:11, you wrote:
> Someone knows where can I find a fast algorithm for calculating mod of
> great powers? (a^e%n, with ' e ' great, but in range of unsigned long int,
> and m in range of unsigned short int)

Command line rulez:

read a; read e; read n; p=$[$a**$e]; echo "p=$p"; x=$[$p/$n]; m=$[$p-$n*$x]; 
echo $m

But you surely want to know a method for this. It's called 'square-and-
multiply', unfortunately google doesn't know much about it.
I'll try to explain.
Store e in binary representation. Store a as a start value s. Now iterate over 
s the following way (along the bits of e):
If the bit is 0, just square s (s := s² % n).
If the bit is 1, also multiply it with a (s := (s² * a) % n).

Example:
a = 5, e = 9, n = 3
5^9 = 1953125, (5^9) % 3 = 2, because:
9 = (1001)bin, thus:
5(1) := 5 (= 2 % 3)
2(10) := 2² (= 1 % 3)
1(100) := 1² (= 1 % 3)
1(1001) := 1²*5 (= 2 % 3)

This method is very common in cryptology.

Josef

-- 
Play for fun, win for freedom.
Linux-Info-Tag Dresden 2003: http://www.linux-dresden.de