Decode RSA given e,p and q_inv ( with respect to p) Suppose I was given e, p and q_inv. Where q_inv = 1 mod (p).
How would one go about computing N to decode the ciphertext?
In RSA $p$ and $q$ are chosen such that they are both prime numbers. I suspect that by $q_{inv}$ you mean the CRT coefficient, which is actually defined as $q_{inv} = q^{-1} \bmod{p}$. Thus, to find $q$ we need to calculate $q_{inv}^{-1} \bmod{p}$, and since $p$ is prime we can use Euler's Theorem to compute it as $q = q_{inv}^{p-2} \bmod{p}$. Note that this only works under the assumption that $p &gt; q$, which is a standard assumption for RSA CRT. Knowing $p$ and $q$, we can now compute $N = p*q$.