classification
Title: pow() should disallow inverse when modulus is +-1
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.9, Python 3.8
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: tim.peters Nosy List: BTaskaya, mark.dickinson, tim.peters
Priority: normal Keywords: patch

Created on 2019-08-20 15:42 by tim.peters, last changed 2019-08-21 00:16 by tim.peters. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 15344 closed BTaskaya, 2019-08-20 16:47
Messages (9)
msg350015 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-08-20 15:42
For example, these should all raise ValueError instead:

>>> pow(2, -1, 1)
0
>>> pow(1, -1, 1)
0
>>> pow(0, -1, 1)
0
>>> pow(2, -1, -1)
0
>>> pow(1, -1, -1)
0
>>> pow(0, -1, -1)
0
msg350016 - (view) Author: Batuhan (BTaskaya) * Date: 2019-08-20 15:53
Can i work on this?
msg350018 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-08-20 15:56
@Batuhan, fine by me if you want to take this on!  It should be relatively easy.  But Mark wrote the code, so it's really up to him.  While I doubt this, he may even argue that it's working correctly already ;-)
msg350021 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-08-20 17:12
> While I doubt this, he may even argue that it's working correctly already ;-)

Yes, I'd argue exactly that. There's nothing ill-defined about working modulo +/-1. Z/1Z is a perfectly-well-defined ring. What's the motivation for this change?
msg350022 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-08-20 17:13
> Z/1Z is a perfectly-well-defined ring.

More to the point, it's a perfectly well-defined ring in which every element is invertible. That's why the Euler phi function has phi(1) = 1 (rather than phi(1) = 0), for example.
msg350024 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-08-20 17:38
Yup, you have a point there! :-)  I guess I'm just not used to 0 being a multiplicative identity.

Don't know what other systems do.  Playing with Maxima, modulo 1 it seems to think 0 is the inverse of everything _except_ for 0.  `inv_mod(0, 1)` returns `false`.  Modulo -1, everything I tried returned `false`.

Which makes less sense to me.

Fine by me if you want to close this as "not a bug".
msg350025 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-08-20 17:47
Mark, to save you the hassle, I'm closing this myself now.  Thanks for the feedback!
msg350030 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-08-20 18:26
> I guess I'm just not used to 0 being a multiplicative identity.

Yes, there's a whole generation of mathematicians who believe (wrongly) that "0 != 1" is one of the ring axioms. But it turns out that excluding the zero ring from the category of (commutative, unital) rings isn't helpful, and causes all sorts of otherwise universal constructs (quotients, localizations, categorical limits in general) to have only conditional existence. So nowadays most (but not all) people accept that the zero ring has the same right to exist as any other commutative ring.

Integral domains are another matter, of course: there you really _do_ want to insist that 1 != 0, though what you're really insisting is that any finite product of nonzero elements should be nonzero, and 1 != 0 is just the special case of that rule for the empty product, while x*y !=0 for x != 0 and y != 0 is the special case for two arguments.
msg350041 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-08-21 00:16
I don't have a problem with the trivial ring - I wasn't being that high-minded ;-)  I was testing a different inverse algorithm, and in the absence of errors checked that

    minv(a, m) * a % m == 1

for various a and m >= 0.  Of course that failed using pow(a, -1, m) instead when m=1.  Offhand, I couldn't imagine a plausible use case for finding an inverse mod 1 - and still can't ;-)  In abstract algebra, sure - but for concrete numerical computation?  Oh well.

In any case, testing

    (minv(a, m) * a - 1) % m == 0

instead appears to work for all non-error cases.
History
Date User Action Args
2019-08-21 00:16:22tim.peterssetmessages: + msg350041
2019-08-20 18:26:03mark.dickinsonsetmessages: + msg350030
2019-08-20 17:47:23tim.peterssetstatus: open -> closed
messages: + msg350025

assignee: tim.peters
resolution: not a bug
stage: patch review -> resolved
2019-08-20 17:38:19tim.peterssetmessages: + msg350024
2019-08-20 17:13:41mark.dickinsonsetmessages: + msg350022
2019-08-20 17:12:07mark.dickinsonsetmessages: + msg350021
2019-08-20 16:47:21BTaskayasetkeywords: + patch
stage: needs patch -> patch review
pull_requests: + pull_request15061
2019-08-20 15:56:49tim.peterssetmessages: + msg350018
2019-08-20 15:53:49BTaskayasetnosy: + BTaskaya
messages: + msg350016
2019-08-20 15:42:42tim.peterscreate