tag:blogger.com,1999:blog-835341608950140555.post4100717355061456049..comments2013-08-13T14:52:46.290+02:00Comments on Numerical Recipes: Modular ExponentiationJaimehttp://www.blogger.com/profile/02831887559711602902noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-835341608950140555.post-84161809703449618082009-03-24T08:44:00.000+01:002009-03-24T08:44:00.000+01:00You are absolutely right. Thanks for the free pyth...You are absolutely right. Thanks for the free python lesson... Calling pow(1234,5678,90) is about 17 times faster than calling the above's modExp(1234,5678,90).<BR/><BR/>I actually wrote this entry thinking that, to compute the multiplicative inverse of a number modulo a prime number, it would be faster to use direct modular exponentiation than to use the extended euclidean algorithm. Well, it wasn't, but for a small factor, but I anyway discarded half the post and code I had written. I have now rechecked, and it seems my intuition was right, since at least for prime modulos smaller than ~50,000, if the modular exponentiation is done without any intermediate redundant function such as mine, direct exponentition is faster than Euclid's...<BR/><BR/>I'm going to have to do some recoding and testing, but your comment is definitely going to require redoing (extending) the entry on the modular multiplicative inverse, and may require extensive rework of the one on wheel factorization, which may also speed up considerably...<BR/><BR/>Thanks!Jaimehttp://www.blogger.com/profile/02831887559711602902noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-59416545334793805542009-03-24T04:14:00.000+01:002009-03-24T04:14:00.000+01:00Interesting article, and interesting blog which I ...Interesting article, and interesting blog which I look forward to reading more of.<BR/><BR/>However, correct me if I am wrong, but the functions described here are redundant for Python users.<BR/>Python has the function<BR/>pow(...)<BR/> pow(x, y[, z]) -> number<BR/><BR/>With two arguments, equivalent to x**y. With three arguments, equivalent to (x**y) % z, but may be more efficient (e.g. for longs).<BR/><BR/>which efficiently (in C) implements modular exponentiation.bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.https://me.yahoo.com/a/bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.#e2bb4noreply@blogger.com