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?

  • $\begingroup$ 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? $\endgroup$ Apr 9, 2019 at 12:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Apr 9, 2019 at 13:35
  • 1
    $\begingroup$ 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... $\endgroup$
    – poncho
    Apr 9, 2019 at 16:56

1 Answer 1


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).

  • $\begingroup$ I should have mentioned that they use a variation of the "usual" Coppersmith techniques. $\endgroup$
    – j.p.
    Apr 9, 2019 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.