# Can we find the exact number given remainder of the numbers with mod m?

I have around 1500 numbers. The numbers $$x_i$$ are calculated as $$x_i$$=($$p*t_i$$) mod m. $$p$$ constant and same for all the numbers while $$t_i$$ are chosen randomly everytime. For example the given numbers $$x_i$$'s are calculated as:

$$x_1$$=($$p*t_1$$) mod m.

$$x_2$$=($$p*t_2$$) mod m.

. . .

$$x_{1500}$$=($$p*t_{1500}$$) mod m.

given $$x_i$$'s and m, can we find the p using above $$x_{i}$$'s ?

• Ah, missread. Let p=1, we found solutions. Let p=2, we found solutions, let p=3, .... – kelalaka Dec 8 '18 at 9:12
• In my case the number m is 3400 bit long and p and t are choosen randomly from (0, m) range. Therefore brute force technique might be very inefficient here. – Ram_Giri Dec 8 '18 at 9:53

## 1 Answer

If you know $$m$$ and the $$x_i$$ but not the $$t_i$$ then there's no way to find $$p$$ in general. For example, suppose that $$m$$ is prime. Then, for any $$p \ne 0$$, there is a set of suitable $$t_i$$, given by $$t_i = p^{-1} x_i$$. The only value for $$p$$ that may be impossible is $$0$$, which is possible only if all the $$x_i$$ are zero.

More generally, the only information you can have about $$p$$ is to rule out certain factors in common with $$m$$. If $$k$$ is a factor of $$m$$ and the $$x_i$$ are not all multiples of $$k$$ then $$p$$ cannot be a multiple of $$k$$ either. That's all the information you have about $$p$$.

(Note that in this answer, I work modulo $$m$$, so e.g. when I write $$p \ne 0$$ I mean $$p \ne 0 \pmod m$$.)