Assume that we have a linear equation like this:
$$ax=b \pmod n$$
when $x$ is the unknown, and $a$ is not an invertible element in $n$.
is finding $x$ a hard problem?
(by solving I mean finding an $x$ that satisfies the equation)
1
-
1$\begingroup$ Please be more specific about what you mean by "solving". There may be multiple solutions (multiple values of $x$ that satisfy the equation). Do you want to find one solution, all solutions, or a specific solution? $\endgroup$– D.W.Mar 3, 2013 at 20:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Calculate $g = GCD(a, n)$ and $n^\prime = n / g$. If $b \not\equiv 0 \pmod g$, then there is no solution.
Divide whole equation by $g$ giving you $a^\prime· x_0 = b^\prime \pmod{n^\prime}$ and solve for $x_0$. Then solutions for $x$ are $x_0 + k· n^\prime$ for $k = 0, 1, ..., g-1$.
answered Mar 2, 2013 at 14:58
$\begingroup$
$\endgroup$
Generally speaking, this problem is computationally easy. It is easy to tell whether a solution exists and, if so, to find at least one.
If you want to find one solution (one $x$ that satisfies the equation), assuming a solution exists, this is easy. @CodesInChaos explains how.
If you want to find all solutions, then it's easy to enumerate all solutions. However, be warned that there will be either 0 or $n/\gcd(a,n)$ solutions. If there are exponentially many solutions, listing all of them will take exponential time.
Finally, if one particular solution is "special" and you want to find it (e.g., maybe Alice choose at random an $x$ satisfying this equation and now challenges you to find it), the best you can do is to guess among all the $n/\gcd(a,n)$ solutions, or enumerate them. If there are exponentially many of them, you may have no way of knowing which one is the "special" one (which one is Alice's).
