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.

  • 1
    $\begingroup$ Random in what set? There is no such thing as a "random number" per se. $\endgroup$ – Robert Israel Apr 19 at 0:35
  • $\begingroup$ I just want a good/reliable way to generate such $x, y, z$ without many trial/errors. So I guess random is bad terminology here. $\endgroup$ – user663014 Apr 19 at 0:39
  • 2
    $\begingroup$ "Efficient" does not have a precise meaning. If you edit the question to tell us why you need this algorithm, how large $n$ is likely to be, how $k$ is chosen and what kind of time constraints you have we may be able to help. $\endgroup$ – Ethan Bolker Apr 19 at 1:06
  • $\begingroup$ If by 'random' you mean that the numbers are to be chosen arbitrarily (without recourse to method), then the notion of any algorithmic method (efficient or otherwise) has been ruled out. I think you want a method, but it's not clear what sorts of methods you wish to exclude. $\endgroup$ – Keith Backman Apr 19 at 2:02

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy