Re: Big Mod algorithm

[Xarvh <xarvh@lombardiacom.it>]

You can also use

E&1

in place of

E%2

I'd suggest you to explicitly replace the operators, since some compilers (an 
old DjGpp comes to mind) do not automatically optimize this way.
I made some bench (all with -O3 optimization), of X/4 vs X>>2, and the 
difference was noticeable.

Note: I successfully tested it with negative numbers: it seemed to work 'cause 
right-shift fills left (upper) bits with the higher bit value:
while 01111100>>2 is 00011111, 11111100>>2 becomes 11111111.
But don't trust this, since is not specifyed by ANSI C and each compiler on 
each platform may behave differently.


Josef Spillner:
>  > 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;
>  > }
>
>  2 remarks:
>  - instead of E/=2, you could also shift (E = E >> 1). Modern compilers
> will recognize this anyway, but it's less ambigous.
>  - make sure you don't use negative values (if they're needed, add
> multiples of N until they're > 0).
>
>  Josef