# In (m mod n = x) how to find m when you know n and x?

So I'm doing some cryptography assignment and I'm dealing with a modular arithmetic in hexadecimal. Basically I have the values for $n$ and the remainder $x$, but I need to find the original number $m$, e.g.

$$m \mod 0x6e678181e5be3ef34ca7 = 0x3a22341b02ad1d53117b.$$

I just need a formula to calculate $m$.

Edit: ok, let's put it this way, $x = K^e \mod n$, I know the values for $x$, $e$ and $n$. Does that help?

Ok, I realized I was approaching the problem in a wrong way, basically I had the RSA public key and I should have used RSA problem to decrypt the file without having the private key. Sorry for the stupid question.

• You need some hypotesis on $m$, otherwise the solution is not unique (in fact, there are infinite solutions) – Exodd Feb 28 '15 at 11:47
• Basically, $x\equiv a\bmod m$ implies $x=a+mk$ for any integer $k$. This should generate all the solutions. – rah4927 Feb 28 '15 at 12:48

## 2 Answers

Unfortunately, I believe that there will be a set of infinite solutions unless specifying some conditions for the solutions.

Consider this example for clarity: 5 mod 2 = 1 ; 7 mod 2 = 1

You see why now? (You can make examples in Hexadecimal also to confirm this)

There are infinitely many solution for $m$ and you need additional information to determine its value.

• ok, let's put it this way, (x = K^e mod n), I know the values for x, e and n. does that help? – Keivan Feb 28 '15 at 11:50
• @Keivan Consider $x=1, n=p\in\mathbb P, e=p-1$. Then every single natural $K$ such that $p\not\mid K$ will satisfy your congruence. – user26486 Feb 28 '15 at 11:55