# About integer factorization

Let $$N=pq$$ where $$p$$ and $$q$$ are safe primes. If the adversary knows the inverse of $$p$$ mod $$q$$ and the inverse of $$q$$ mod $$p$$, can this help him factor $$N$$ or break the textbook RSA?

• Well the point is that you can't calculate $p \bmod q$ because you don't have $p$ and $q$, or did I understand something wrong in your question? – AleksanderRas Apr 9 '19 at 12:44
• The adversary is assumed to know $p^{-1}\bmod q$. But is s/he assumed to additionally know $q^{-1}\bmod p$, or $q\bmod p$ ? The question (v2) can be read either way. – fgrieu Apr 9 '19 at 13:35
• I'm pretty sure that $q^{-1} \bmod p$ is meant; if you know $q \bmod p$ (where $q < p$), well, that fairly obviously gives the game away... – poncho Apr 9 '19 at 16:56

Santanu Sarkar and Subhamoy Maitra show in Some Applications of Lattice Based Root Finding Techniques the deterministic polynomial time equivalence between factoring $$N$$ ($$N=p\cdot q$$, where $$p>q$$ or $$p,q$$ are of same bit size) and knowledge of $$q^{−1} \bmod p$$ (cited from the abstract).