Home Original page

bpo-36027: Extend three-argument pow to negative second argument by mdickinson · Pull Request #13266 · python/cpython

Conversation

@mdickinson

This PR allows the built-in pow to compute modular inverses, by providing a negative second argument:

>>> pow(7, -1, 100)  # inverse of 7 modulo 100
43
>>> pow(2, -5, 101)  
60

https://bugs.python.org/issue36027

ZackerySpytz

/* if exponent is negative, negate the exponent and
replace the base with a modular inverse */
if (Py_SIZE(b) < 0) {
temp = (PyLongObject *)_PyLong_Copy(b);

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think Py_SETREF() should be used in this block.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'd rather keep it the way it is in this PR, for consistency with the existing previous block that negates the modulus. I'm happy to make a separate PR that updates both blocks (and other uses in longobject.c) to use Py_SETREF, but I don't want the long_pow code to be doing the same thing in two different ways in two places, and I want to keep this particular PR focused on the inversion feature.

@jdemeyer

I don't quite like the wording in the documentation as this isn't about the pow() operator but about the implementation of int.__pow__. The pow() operator doesn't have any restrictions about its arguments.

@mdickinson

@jdemeyer Agreed. I've updated the wording to make it clearer that this feature applies only for int operands.

mdickinson

…ltin, remove accidental spacing change.

rhettinger
For :class:`int` operands *x* and *y*, if *z* is present, *z* must also be
of integer type and *z* must be nonzero. If *z* is present and *y* is
negative, *x* must be relatively prime to *z*. In that case, ``pow(ix, -y,

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Consider changing ix to inv_x for readability.

For :class:`int` operands *x* and *y*, if *z* is present, *z* must also be
of integer type and *z* must be nonzero. If *z* is present and *y* is
negative, *x* must be relatively prime to *z*. In that case, ``pow(ix, -y,
z)`` is returned, where *ix* is an inverse to *x* modulo *z*.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Perhaps this needs an example for clarity:

# Multiplicative inverse of 38 in mod 97
>>> pow(38, -1, 97)
23
>>> 23 * 38 % 97 == 1
True

donhatch

/* Compute an inverse to a modulo n, or raise ValueError if a is not
invertible modulo n. Assumes n is positive. The inverse returned
is whatever falls out of the extended Euclidean algorithm: it may
be either positive or negative, but will be smaller than n in

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh my, the "it may be either positive or negative" is alarming!
When I first read this, I feared you might have used the result of this utility function directly, making pow(5, -1, 8) return -3.
I see you didn't, but maybe a word of reassurance here would be helpful!

donhatch

}
Py_DECREF(a);
a = n;
n = r;

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Seems like you could skip the final round of arithmetic (the long_mul and long_sub) used to update c, by leaving the loop early at this point if the remainder is 0, right?
Just make sure to update b on the way out.

DinoV pushed a commit to DinoV/cpython that referenced this pull request

Jan 14, 2020

Labels