RSA: unknown public exponents
Hint: seen as a discrete logarithm problem, there's an attack of cost $O(\sqrt{\min(e_1,e_2)})$.

I see no improvement on the asymptotic cost without factoring $n$.

Update: I think it is rigorously provable that if one could solve this problem in polynomial time with sizable probability for proper choice of $n$ and random other parameters, then we could factor $n$. Proof is left as an exercise to the reader by the usual method: invoke the hypothetical algorithm solving the problem in a polynomial-time algorithm that factors $n$.