[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

*To*: <linuxgames@sunsite.dk>*Subject*: Re: Big Mod algorithm*From*: "Igor Cabral Corrêa" <imortis@uol.com.br>*Date*: Sun, 17 Aug 2003 16:49:25 -0300*Delivered-to*: archiver@seul.org*Delivered-to*: mailing list linuxgames@sunsite.dk*Delivery-date*: Sun, 17 Aug 2003 15:46:29 -0400*Mailing-list*: contact linuxgames-help@sunsite.dk; run by ezmlm*References*: <002001c364e2$94e18520$0100000a@knight> <200308172005.21389.josef@ggzgamingzone.org>*Reply-to*: linuxgames@sunsite.dk

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

**Follow-Ups**:**Re: Big Mod algorithm***From:*Josef Spillner <dr_maux@users.sourceforge.net>

**References**:**Big Mod algorithm***From:*Igor Cabral Corrêa <imortis@uol.com.br>

**Re: Big Mod algorithm***From:*Josef Spillner <dr_maux@users.sourceforge.net>

- Prev by Author:
**Re: wings3d** - Next by Author:
**Static Linking Throuble with OpenGL** - Previous by thread:
**Re: Big Mod algorithm** - Next by thread:
**Re: Big Mod algorithm** - Index(es):