# Re: Big Mod algorithm

```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:

echo \$m

But you surely want to know a method for this. It's called 'square-and-
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

--