[Python-Dev] negative modular exponentiation (original) (raw)

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