Python. RSA common modulus attack problem I have:

N = /*500 decimal numbers*/

E1 = 3740453

E2 = 4226171

M^E1 = /*500 decimal numbers*/

M^E2 = /*500 decimal numbers*/


I must use RSA common modulus attack on it.

Using gmpy2.gcdext() i have:

a = 624366
b = -552607


So E1*a+E2*b == 1 is True.

Now i need to know M. For this i must to do follow things:

M = ((M^E1)^a) * ((M^E2)^b) #Just a formula...


In python 2.7 i do like that:

M = pow(ME1,a) * pow(ME2, b) #Where ME1 = M^E1, and ME2 = M^E2


And i have a problem here!
Function pow() can't work with negative "b".

How can i calculate last expression ?
I have solved this problem. @fgrieu  was right! Thanks for him and other!

Calculating modular inverse

if a &lt; 0:
    _, eM1, __ = gmpy2.gcdext(eM1, N)
elif b &lt; 0:
    _, eM2, __ = gmpy2.gcdext(eM2, N)


Calculating source message M

M1 = pow(eM1, abs(a), N) #I just realized, that always i need to use modulus pow(a,b,n)
M2 = pow(eM2, abs(b), N) #In this way all calculations are really fast!
M = (M1 * M2) % N # And final multiplication uses modulus same as previous expression