[issue936813] fast modular exponentiation

Mark Dickinson added the comment: Okay, I retested the original patch without any of my refactoring (besides fixing the twodigits cast), and got pretty much the same numbers. On a 32-bit non-debug trunk build (still on OS X 10.6), I get: Unpatched - Mark-Dickinsons-MacBook-Pro:trunk

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: One more lot of timings, from Trevor's pow_benchmark.txt: Unpatched - 1024 bits: 0.008256 2048 bits: 0.052324 3072 bits: 0.159689 4096 bits: 0.357264 Patched (percent speedup) --- 1024 bits: 0.006576 (+25.5%) 2048 bits: 0.045878 (+14.1%) 3072 bit

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: Hmm. For smaller inputs, I'm actually getting significant slowdowns: Unpatched: >>> timeit('pow(123, 123456789, 123456789L)') 7.355183839797974 Patched: >>> timeit('pow(123, 123456789, 123456789L)') 8.873976945877075 -- ___

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: Some timings on my machine (OS X 10.6, 64-bit nondebug build, trunk r77157). These are just doing an RSA-like powmod pow(c, d, n), with n the product of two similarly-sized primes, d the inverse of 7 modulo eulerPhi(n), and c of similar magnitude to n. Wit

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: Here's a second revision of Trevor's patch: - factor out the code for creating Montgomery representatives; this simplifies the changes to the main long_pow function - get rid of l_invmod and use a simple function for computing the negation of an invers

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: Here's a slightly modified version of Trevor's patch: - update to apply cleanly to trunk - fix misplaced twodigits cast described above - add 'PyLong_' prefix to BASE, MASK and SHIFT - no need for _PyLong_Copy in l_invmod: just copy and INCREF the point

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: Looks like the test failure is a result of a misplaced (twodigits) cast: replacing the line carry += (twodigits) ( (*aptr) + (u * (*mptr++)) ); in function mont_reduce with carry += *aptr + (twodigits)u * *mptr++; fixes this. -- ___

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: This patch still(!) applies almost perfectly cleanly to trunk. On a 64- bit machine, I'm getting a failure in test_auto_overflow, coming from: >>> pow(0L, 0, 9223372036854775807) 28051505152L I haven't looked hard to figure out where this is coming from, but

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: By the way, I'd be interested to know if you (Trevor) have any thoughts on the multiplication optimizations that are in the patch 30bit_longdigit13+optimizations.patch in the issue 4258 discussion. These have been giving me some quite spectacular speedups (4

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: Thanks, Trevor. I'm currently working on the 15-bit -> 30-bit digit change (issue 4258), since it seems sensible to get that in before considering other optimizations, but I certainly hope to find time to look at this before the 3.1 release cycle gets underw

[issue936813] fast modular exponentiation

Changes by Gregory P. Smith : -- nosy: +gregory.p.smith ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http:/

[issue936813] fast modular exponentiation

Trevor Perrin added the comment: Hi Mark, Let me know if I can give you any help with this. The original patch was split into 3 parts. The only part remaining unapplied is the Montgomery Reduction. It appeared to be a significant speedup when I was last testing, and is frequently used in o

[issue936813] fast modular exponentiation

Mark Dickinson added the comment: I'll see if I can find time to look at this; I'm currently looking at various ways to improve long integer arithmetic in 2.7/3.1. -- assignee: tim_one -> marketdickinson ___ Python tracker

[issue936813] fast modular exponentiation

Changes by Daniel Diniz : -- stage: -> patch review versions: +Python 2.7, Python 3.1 -Python 2.6, Python 3.0 ___ Python tracker ___ ___

[issue936813] fast modular exponentiation

Christian Heimes added the comment: Mark, as the second math guru in our team, you are probably interested in these patches. Trevor has written an interesting patch to optimize longs for cryptographic problems. In fact it might be two patches now, one for the Montgomery Reduction and one containi

[issue936813] fast modular exponentiation

Christian Heimes added the comment: Re-targeting for 2.6 We should discuss it at the bug day. -- nosy: +tiran type: -> rfe versions: +Python 2.6 -Python 2.5 Tracker <[EMAIL PROTECTED]> ___