Given a modulus $N$ and an integer $k \in [0, N)$ I'd like to "factor" $k$ into two values $a$ and $b$ both in $[0, N^{1/2 + \epsilon})$. I put quotes around "factor", because multiplying $a$ and $b$ together only needs to give $k$ when working modulo $N$.
Is it possible to efficiently find such values for any $k$ and $N$? Are they even guaranteed to exist?
One indicator that it might be easy to find these values is that the extended euclidean algorithm nearly does the trick. Amongst the numbers produced during intermediate states of the algorithm, you can find values $a$ and $b$ of size roughly $\sqrt{N}$ satisfying $a \cdot b^{-1} \equiv k \pmod{N}$, where $b^{-1}$ is the multiplicative inverse of $b$ modulo $N$ [1]. But I don't want a small value of $b$ whose inverse is part of the "factorization", I want $b$ itself to be the factor.