Why the different results when using external modulus than built-in pow(x, y, mod) in Python 3.9

user_15403890 0
Viewed 62

While watching John Hammond's YouTube video about "Modular Inverses in Python 3 (PicoCTF 2022 #03 basic-mod2)" I discovered the newer version of pow(x, y, mod) function in Python 3.9, which adds modulus before returning the answer.

He was using -1 for the power, as in pow(x, -1, 41). I decided to experiment with a few values of x and got some surprising answers, then I used the same values but did the modulus in a separate way, like pow(x, -1) % 41 and got different answers.

Can anyone explain why the answers are different?

for x in range(2, 7):
    a = pow(x, -1, 41)
    b = pow(x, -1) % 41 
    print(f'{a:4} {b}')

results='''
  21 0.5
  14 0.3333333333333333
  31 0.25
  33 0.2
   7 0.16666666666666666
'''
negative-number pow modulo python
1 Answers

I think you are looking for this piece of docs on the built-in pow() (implemented here):

For int operands base and exp, if mod is present, mod must also be of integer type and mod must be nonzero. If mod is present and exp is negative, base must be relatively prime to mod. In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.

Here’s an example of computing an inverse for 38 modulo 97:

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

(source, since 3.8)

Edit:

By digging through the C code you'll eventually get from PyNumber_Power() to the long_pow() which is the real implementation i.e. the maths behind it. The comments within the code explain it, but I'll put it here in case it changes in the future:

First, a bit of local renaming:

long_pow(PyObject *v, PyObject *w, PyObject *x)
PyLongObject *a, *b, *c; /* a,b,c = v,w,x */

  • pow(a, b < 0, None):

    if exponent is negative and there's no modulus return a float. This works because we know that this calls float_pow() which converts its arguments to double. (source)

  • pow(a, b < 0, c < 0):

    modulus < 0:

    negativeOutput = True

    modulus = -modulus (source)

  • pow(a, b < 0, c == 0):

    if modulus == 1:

    return 0 (source)

  • pow(a, b < 0, c > 0): (your case)

    if exponent is negative, negate the exponent and replace the base with a modular inverse (source)

after those conditions the calculations take place and those are intertwined with optimizations so it's harder reading than just a single formula.

Now to explain a modular inverse, it'd rather check Wolfram's MathWorld article and why pow() is implemented that way.

Also a minor thing about modulo, what you expect happening is in fact never happening because the calculation itself can't happen for that case, or better said yields the original input, and for the rest the implementation will prevent you to do so:

have N != 0, M != 0
N ** -1 <=> pow(N, -1) <=> 1 / N

but
(N ** -1) % M <!=> pow(N, -1, M)

because
0 < (N ** -1) < 1
0 < (1 / N) < 1
and
(1 / N) < M, so you get (1 / N) % M <=> 1 / N

and the pow() is calculating a different concept
(what * N) % M == 1

hence:

>>> 1 / 38
0.02631578947368421  # < 1, > 0

>>> pow(38, -1, 97)  # (what * N) % M == 1?
23  # == what
>>> (23 * 38) % 97
1

>>> 1 / 38
0.026_315_789_473_684_21
>>> (1 / 38) % 0.02  # N > M
0.006_315_789_473_684_209

>>> pow(38, -1, 0.02)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: pow() 3rd argument not allowed unless all arguments are integers

but, there's a more consistent way

>>> from math import fmod
>>> 1 / 38
0.026_315_789_473_684_21
>>> 38 ** -1
0.026_315_789_473_684_21
>>> pow(38, -1)
0.026_315_789_473_684_21

>>> fmod(1 / 38, 97)  # still N < M, so kind of useless
0.026_315_789_473_684_21
>>> fmod(38 ** -1, 95)
0.026_315_789_473_684_21
>>> fmod(pow(38, -1), 95)
0.026_315_789_473_684_21

>>> (1 / 38) % 0.02  # N > M, so something useful happens
0.006_315_789_473_684_209
>>> fmod(1 / 38, 0.02)
0.006_315_789_473_684_209
>>> fmod(38 ** -1, 0.02)
0.006_315_789_473_684_209
>>> fmod(pow(38, -1), 0.02)
0.006_315_789_473_684_209
user_59940410
Related