What is an efficient way to choose three numbers $x, y, z$ such that $xyz \equiv k \pmod{n}$, where $k, n$ are given?
I was thinking about choosing $x$ and $y$ randomly and then computing an inverse for $z$; however, I realized that there's no guarantee that this inverse exists. So, I'm not so sure if this is an efficient way anymore.
Note that I don't want to just choose three random numbers and see if their product is congruent to $x$ (and try again if not). I'm wondering if there's some efficient way to do this.
Let's say you want $x, y, z$ to be in the integers mod $n$. The simplest case is if $\gcd(k,n)=1$. Then $x$ and $y$ can be anything coprime to $n$, and $z \equiv k(x y)^{-1} \ (\bmod n)$.
More generally, suppose $gcd(k,n) = g > 1$. Then take any $g_1, g_2, g_3$ so that $g = g_1 g_2 g_3$, any $h_1, h_2$ coprime to $n/g$, let $h_3 \equiv (k/g) (h_1 h_2)^{-1} \ (\bmod (n/g)$, and take $x = g_1 h_1$, $y = g_2 h_2$, $z = g_3 h_3$.