[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