Re: Big Mod algorithm

["Igor Cabral Corrêa" <imortis@uol.com.br>]

Josef,

Could you please check if I understood correclty? Is this in C?

unsigned long int mod(unsigned long int A,unsigned long int E,unsigned int
N){
    unsigned long int S=A;
    while (E){
        if (E%2) S=((S*S)*A)%N;
        else S=(S*S)%N;
        E/=2;
    }
    return S;
}


[]Žs
Igor

----- Original Message -----
From: "Josef Spillner" <dr_maux@users.sourceforge.net>
To: <linuxgames@sunsite.dk>
Sent: Sunday, August 17, 2003 3:07 PM
Subject: Re: Big Mod algorithm


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