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

*To*: linuxgames@sunsite.dk*Subject*: Re: Big Mod algorithm*From*: Josef Spillner <dr_maux@users.sourceforge.net>*Date*: Sun, 17 Aug 2003 20:07:48 +0200*Delivered-to*: archiver@seul.org*Delivered-to*: mailing list linuxgames@sunsite.dk*Delivery-date*: Sun, 17 Aug 2003 14:08:39 -0400*In-reply-to*: <002001c364e2$94e18520$0100000a@knight>*Mailing-list*: contact linuxgames-help@sunsite.dk; run by ezmlm*References*: <002001c364e2$94e18520$0100000a@knight>*Reply-to*: linuxgames@sunsite.dk*User-agent*: KMail/1.5.9

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:*"Igor Cabral Corrêa" <imortis@uol.com.br>

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

- Prev by Author:
**Re: Blender & Cygwin** - Next by Author:
**Re: Big Mod algorithm** - Previous by thread:
**Big Mod algorithm** - Next by thread:
**Re: Big Mod algorithm** - Index(es):