[issue936813] fast modular exponentiation

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> 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
   pointers
 - don't calculate d - q*c by hand in l_invmod, since l_divmod computes
   the remainder already
 - simplify reference counting in l_invmod
 - add a '* 1U' to a digit-by-digit multiplication, to avoid possible
   (in theory;  unlikely in practice) undefined behaviour resulting
   from signed integer overflow.

The rest of the patch looks fine to me, modulo some minor style issues.

Two points:

- it seems that l_invmod is only ever used to compute the inverse of a 
single-digit long modulo PyLong_BASE.  Mightn't it be more efficient to 
simply do a twodigit/digit-based calculation here instead, to reduce the 
overhead of setting up the Montgomery reductions?

- the current algorithm for three-argument pow involves many allocations 
and deallocations of integers;  it seems to me that these could almost 
all be eliminated:  for pow(a, b, c) with c an n-digit PyLong, just 
allocate 2*n (or possibly 2*n+1) digits of workspace to begin with and 
use that to store intermediate products;  the Montgomery reduction could 
then be done more-or-less in place.  This doesn't work with the non-
Montgomery method, though, since l_divmod doesn't operate in place.

----------
Added file: http://bugs.python.org/file15703/long_pow_2009_12_30.diff

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue936813>
_______________________________________