About integer factorization
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&gt;q$ or $p,q$ are of same bit size) and knowledge of $q^{−1} \bmod p$ (cited from the abstract).