pythonpython-3.xrsapow

Python pow function not returning correct values for large numbers?

I'm trying to use values generated by an RSA algorithm in python by using python's pow function with 3 arguments but it doesn't seem to be returning correct values for large numbers. For example if I try to do it with a small number, like 42:

n=10002668571558232229090995822943
e=65537
d=3132501789258907532830941079073


number=pow(42,e,n)
print(number)
number=pow(number,d,n)
print(number)

The output is:

8057039574873290190626687506928

42

But when I try it with a big number:

n=10002668571558232229090995822943
e=65537
d=3132501789258907532830941079073


number=pow(1691472818829646266231812146685797,e,n)
print(number)
number=pow(number,d,n)
print(number)

I get this output:

4303635339538819794578326868533

1021830236305019515433852608430

where I am expecting the second number to be 1691472818829646266231812146685797.

I've tried looking online for solutions but I can't seem to find a solution to this. Any help would be appreciated.

Solution

  • As commented by @President you are getting the correct result:

    Please see the document:

    https://docs.python.org/3/library/functions.html#pow

    n=10002668571558232229090995822943
e=65537
d=3132501789258907532830941079073


number = pow(1691472818829646266231812146685797,e,n)

print(number)

#output
4303635339538819794578326868533

    Return base to the power exp; if mod is present, return base to the power exp, modulo mod (computed more efficiently than pow(base, exp) % mod). The two-argument form pow(base, exp) is equivalent to using the power operator: base**exp.

    Also, I did manually,

    m = 1691472818829646266231812146685797 ** e    #this will take some time depending upon your machine

print(m % n)

#output

4303635339538819794578326868533

    Edit:

    Please see this article:

    https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Encryption

    It only works when your number is less than n

    e.g.

    n=10002668571558232229090995822943
e=65537
d=3132501789258907532830941079073

number=pow(42,e,n)
print(number)
number=pow(number,d,n)
print(number)

#output (you get 42 back in the output)

8057039574873290190626687506928
42

    because :

    42 < 10002668571558232229090995822943

    Now, take the next example:

    n=10002668571558232229090995822943
e=65537
d=3132501789258907532830941079073

number=pow(1691472818829646266231812146685797,e,n)
print(number)
number=pow(number,d,n)
print(number)

#output (you don't get 1691472818829646266231812146685797 back in the output)

4303635339538819794578326868533
1021830236305019515433852608430

    because:

    1691472818829646266231812146685797 > 10002668571558232229090995822943