[Python-Dev] negative modular exponentiation

Guido van Rossum guido at python.org
Tue May 4 11:33:53 EDT 2004


> SF patch 936813 (fast modular exponentiation) introduces some
> optimization of exponentiation with longs, including a new feature:
> in a pow(x,y,z), the exponent y is allowed to be negative when it
> makes mathematical sense.  The result of (x ** -y) % z is a number
> that is the inverse of (x ** y) % z, i.e. multiplying the two gives
> 1 modulo z.  This is a very convenient feature if you are doing
> modulo arithmetic.  Quoting Trevor Perrin, the patch's author:
> 
>   Libraries like GMP and LibTomMath work the same way.
>   Being able to take inverses mod a number is useful for
>   cryptography (e.g. RSA, DSA, and Elgamal).
> 
> As this is a new feature it should be approved of.  If it is, I'd
> volunteer to review the patch and make the necessary extension to
> the plain integer's pow() so that they work the same way.
> 
> E.g.
> 
> >>> pow(2,-1,9)
> 5
> 
> because (5*2)%9 == 1.  Currently this gives a TypeError (why not a
> ValueError?) so changing the behaviour seems safe.

This seems of little practical value (especially since real crypto
wizards only complain that Python's longs are so much slower than
gmp), but I can't see it could possibly break something, so a +0 from
me.  (Hm, it could break the expectation that pow(x, y, z), when
defined, equals x**y%z.  At the very least the docs need to be
updated.)

--Guido van Rossum (home page: http://www.python.org/~guido/)



More information about the Python-Dev mailing list