Logged In: YES 
user_id=31435

Notes after a brief eyeball scan:

Note that the expression

a & 1 == 1

groups as

a & (1 == 1)

in C -- comparisons have higher precedence in C than bit-
fiddling operators.  Stuff like that is usually best resolved by 
explicitly parenthesizing any "impure" expression fiddling with 
bits.  In this case, in a boolean expression plain

a & 1

has the hoped-for effect. and is clearer anyway.

Would be better to use "**" than "^" in comments when 
exponentiation is intended, since "^" means xor in both 
Python and C.

Doc changes are needed, because you're changing visible 
semantics in some cases.

Tests are needed, especially for new semantics.

l_invmod can return NULL for more than one reason, but one 
of its callers ignores this, assuming that all NULL returns are 
due to lack of coprimality.  It's unreasonable to, e.g., replace 
a MemoryError with a complaint about coprimality; this needs 
reworking.  l_invmod should probably set an exception in 
the "not coprime" case.  As is, it's a weird function, 
sometimes setting an exception when it returns NULL, but not 
setting one when coprimality doesn't obtain.  That makes life 
difficult for callers (which isn't apparent in the patch, 
because its callers are currently ignoring this issue).

The Montgomery reduction gimmicks grossly complicate this 
patch -- they're long-winded and hard to follow.  That may 
come with the territory, but it's the only part of the patch 
that made me want to vomit <wink>.  I'd be happier if it 
weren't there, for aesthetic, clarity, and maintainability 
reasons.   How much of a speedup does it actually buy?

You're right that int pow must deliver the same results as 
long pow, so code is needed for that too.  "short int" 
versus "unbounded int" is increasingly meant to be an invisible 
internal implementation detail in Python.  I'm also in favor of 
giving this meaning to modular negative exponents, btw, so 
no problem with that.  An easy way would be to change int 
pow to delegate to long pow when this is needed.

Pragmatics:  there's a better chance of making 2.4 if the 
patch were done in bite-size stages.  For example, no doc 
changes are needed to switch to 5-ary left-to-right 
exponentation, and that has no effect on the int 
implementation either, etc.  A patch that did just that much 
probably would have gone in a long time ago.