1. ## Solving modular inequality

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

A solution is a $c$ such that :

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

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

This seems impossible somehow.

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

A solution is a $c$ such that :

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

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

This seems impossible somehow.
I assume $a\geq0$?