Originally Posted by

**Bacterius** Hello,

I'm trying to solve the following inequality efficiently. I am given a composite number $\displaystyle n$ with unknown factorization (it shall not be attempted to factor it), and a composite number $\displaystyle k$ with known factorization. What is more, $\displaystyle \varphi{(k)}$ is known along with its factorization.

A solution is a $\displaystyle c$ such that :

$\displaystyle c^{\varphi{(k)}} \equiv a \pmod{kn}$

And $\displaystyle a < \sqrt[\left \lceil \ln{k} \right \rceil]{kn}$.

This seems impossible somehow.