Re: Big Mod algorithm

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

Boa tarde Igor,

Am Sonntag, 17. August 2003 21:49 schrieben Sie:
> Josef,
>
> Could you please check if I understood correclty? Is this in C?

Sorry for the delay, but I'm currently not at home...

So, yes, it looks good (and works correctly).

> 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

-- 
Josef Spillner - KDE Developer's Conference - "Kastle 2003" - 21.-30.08.2003
Institute of Physical Biology :: University of South Bohemia :: Nové Hrady