Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)

share|improve this question
1  
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? –  D.W. Mar 3 '13 at 20:05
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.