Negative power in modular pow()

Question

How can we use pow with a negative exponent in a modular context?

pow(x, y, [z]) If z is present, x and y must be of integer types, and y must be non-negative.

>>> pow(11444, -357)
0.0
>>> pow(11444, -357) % 48731
0.0
>>> pow(11444, -357, 48731)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: pow() 2nd argument cannot be negative when 3rd argument specified

In my use case, I want to encrypt a message using a Schnorr scheme:

y = (g ** -w) mod p

but pow won't accept a negative number as the second argument here. As an example, from

g = 11444
p = 48731
w = 357

y should be 7355.

Sorry, what? Do you have an actual question, preferably with an [mcve] for us so we can provide an answer to it? — Martijn Pieters, Dec 06 '15 at 15:31
`pow(10, -2)` produces `0.01`, for example, so your statement that *python won't work with negative number* is at the very least a misunderstanding on your part. — Martijn Pieters, Dec 06 '15 at 15:33
I think what he means is that the lacking precision for very small numbers will yield a `0.0`. — Pallav Agarwal, Dec 06 '15 at 15:34
I think what the OP is really wondering is "does Python automatically compute the modular multiplicative inverse to support taking negative modular powers?" and the answer is no. g^-1 mod p is 29420, and `pow(29420, 357, 48731) == 7355`; you need to compute 29420 yourself (e.g. using the extended Euclidean method.) — DSM, Dec 06 '15 at 15:42
Thanks @DSM, But I'm not answer "does it" nor "How". At least will read for extended Euclidean method you advised. — kAldown, Dec 06 '15 at 15:48
@DSM: I've reopened this after an edit by the OP, but your explanation is a lot better. You could edit that into the question perhaps. — Martijn Pieters, Dec 06 '15 at 15:52
I think that pretty fine to close question. If @DSM wants, I can toggle his answer as right, using [link](https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm) — kAldown, Dec 06 '15 at 15:55

score 9 · Answer 1 · answered Nov 06 '19 at 14:51

9

As of python 3.8 you can do this. 3.9 adds keyword arguments. Check out there code here. There usage is

>>> pow(38, -1, mod=97)
23
>>> 23 * 38 % 97 == 1
True

answered Nov 06 '19 at 14:51

A_Arnold

3,195
25
39

score 6 · Accepted Answer · edited May 23 '17 at 11:54

6

pow won't automatically compute a modular multiplicative inverse for you. Instead, we can compute it ourselves (say via the extended Eulidean algorithm) and then rewrite pow(a,-b,c) as pow((a^-1) mod c, b, c). Stealing the MMI code from this question:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

we get

>>> g = 11444
>>> p = 48731
>>> w = 357
>>> modinv(g, p)
29420
>>> pow(modinv(g, p), w, p)
7355

edited May 23 '17 at 11:54

Community

1
1

answered Dec 06 '15 at 16:03

DSM

342,061
65
592
494

2

In the case where `p` is prime (as it is here), a simpler implementation for `modinv(a, p)` is `pow(a, p-2, p)`. – interjay Dec 06 '15 at 16:11
New in python3.8: `pow` can now compute a modular multiplicative inverse. https://docs.python.org/3/library/functions.html#pow – Stef Jan 11 '22 at 15:26

Negative power in modular pow()

2 Answers2

Linked