Let $c = m^e \mod N$ be a RSA-ciphertext with $N = pq$.
Let $m_p = m \mod p$ be known
Knowing this, how can i reconstruct $m$ in polynomial time with respect to $log N$ and $log e$ ?
I suspect it might have to do with chinese remainder theorem, but i am not entirely sure. I know we need to find m, such that
$gcd(m - m_p, N) = p$, but i dont quite see, how we can do that in polynomial time