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.

`0.5` would be the answer, but why does wolfram alpha provide the answer I was looking for ? — mrcdnk, Nov 23 '15 at 19:49
That's a good question. Although it's not related to python because this is the expected behavior. — Saeid, Nov 23 '15 at 19:51
Typing `(1/211) mod ((199 - 1)*(337 - 1))` into Alpha gives the Python answer: roughly, `0.00473` — jme, Nov 23 '15 at 19:55

score 11 · Accepted Answer · edited May 23 '17 at 10:30

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

score 5 · Answer 2 · answered Nov 23 '15 at 19:54

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.

score 1 · Answer 3 · edited Apr 13 '17 at 12:19

1

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

edited Apr 13 '17 at 12:19

Community

1
1

answered Nov 23 '15 at 19:53

nichochar

2,720
1
18
16

score 0 · Answer 4 · answered Nov 24 '15 at 00:14

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.

Python modulo result differs from wolfram alpha?

4 Answers4