RetroSearch Browse

Tue May 4 10:58:52 EDT 2004 · http://mail.python.org/pipermail/python-dev/2004-May/044659.html

Hello,

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.

Armin

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://mail.python.org/pipermail/python-dev/2004-May/044659.html below:

[Python-Dev] negative modular exponentiation