Python modulo result differs from wolfram alpha?

Question

When I run my python 3 program:

exp = 211
p = 199
q = 337

d = (exp ** (-1)) % ((p - 1)*(q - 1))

results in 211^(-1).

But when I run the calculation in wolfram alpha I get the result I was expecting.

I did some test outputs and the variables exp, p and q in the program are all the integer values I used in wolfram alpha.

My goal is to derive a private key from a (weakly) encrypted integer. If I test my wolfram alpha result, I can decrypt the encrypted message correctly.

Answer 1

Wolfram Alpha is computing the modular inverse. That is, it's finding the integer x such that

exp*x == 1 mod (p - 1)*(q - 1)

This is not the same as the modulo operator %. Here, Python is simply calculating the remainder when 1/exp is divided by (p - 1)*(q - 1) when given the expression in your question.

Copying the Python code from this answer, you can compute the desired value with Python too:

>>> modinv(exp, (p - 1)*(q - 1))
45403

Answer 2

Wolfram Alpha does not have well-defined syntax. It takes arbitrary text you provide and attempts to figure out what you meant by that input. In this case, it decided you were probably looking for a modular inverse, and it gave you one.

Python has well-defined syntax. In Python, the parser does not take the ** and the % together and guess that that combination makes the two operators have a meaning other than their usual meaning. The ** is computed the usual way, and then % is the modulo operator. If you want a modular inverse, you'll have to write one yourself.

Answer 3

I think the idea here is that wolfram alpha and python define the modulo operation differently depending on the fact that you are dealing with integers or real numbers. In this case, Wolfram Alpha is using the modulo inverse because it detects the first number is 0 < x < 1

More information about the definition on real numbers here