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.

Submarginal

This seems logical. What do you expect 0.5 % 2 to be ? – Outpost

0.5 would be the answer, but why does wolfram alpha provide the answer I was looking for ? – Submarginal

That's a good question. Although it's not related to python because this is the expected behavior. – Outpost

Typing (1/211) mod ((199 - 1)*(337 - 1)) into Alpha gives the Python answer: roughly, 0.00473 – Ikon

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

Hypolimnion

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.

Salamander

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

Fortyniner

Answer 4

Python evaluates immediately (211^(-1) gets computed as 0.004739... and not ekpt as 1/211) and the modular Euclidan remainder for x and y is conventinally defined as x-floor(x/y)*y if any of x,y is a rational number. If you do your calculation with some dedicated number theoretic program like e.g.: GP/Pari

ep = 211;p = 199;q = 337;(ep ^ (-1)) % ((p - 1)*(q - 1))

you will get the result you expected to get because a) it keeps fractions as fractions as long as possible and b) knows about modular arithmetic.

Is you like Python you may take a look at the programms an libraries offered at SciPy. SymPy might be what you are looking for.

Crystallization