As shown above, if we calculate pow(m, e)mod(p * q)with m = 6574839, we get c = 3893595

Normally, we can find the value of m by following these steps:

(1) Calculate the modular inverse of e.
We can make use of the following equation, d = e^(-1)(mod lambda(n)),
where lambda is the Carmichael Totient function.
Read: Carmichael function

(2) Calculate m = pow(c, d)mod(p * q)

(3) We can perform this calculation faster by using the Chinese Remainder Theorem,
as defined below in the function
Further reading on Chinese Remainder Theorem can be done at
RSA (cryptosystem)

Below is the Python implementation of this approach :

# Function to find the gcd of two 

# integers using Euclidean algorithm

def gcd(p, q):

    if q == 0:

        return p

    return gcd(q, p % q)

# Function to find the

# lcm of two integers 

def lcm(p, q):

    return p * q / gcd(p, q)

# Function implementing extended

# euclidean algorithm

def egcd(e, phi):

    if e == 0:

        return (phi, 0, 1)

    else:

        g, y, x = egcd(phi % e, e)

        return (g, x - (phi // e) * y, y)

# Function to compute the modular inverse

def modinv(e, phi):

    g, x, y = egcd(e, phi)

    return x % phi

# Implementation of the Chinese Remainder Theorem

def chineseremaindertheorem(dq, dp, p, q, c):

    # Message part 1

    m1 = pow(c, dp, p)

    # Message part 2

    m2 = pow(c, dq, q)

    qinv = modinv(q, p)

    h = (qinv * (m1 - m2)) % p

    m = m2 + h * q

    return m

# Driver Code

p = 9817

q = 9907

e = 65537

c = 36076319

d = modinv(e, lcm(p - 1, q - 1))

"""

pow(a, b, c) calculates a raised to power b 

modulus c, at a much faster rate than pow(a, b) % c

Furthermore, we use Chinese Remainder Theorem as it

splits the equation such that we have to calculate two

values whose equations have smaller moduli and exponent  

value, thereby reducing computing time.

"""

dq = pow(d, 1, q - 1)

dp = pow(d, 1, p - 1)

print chineseremaindertheorem(dq, dp, p, q, c)

Output :

41892906