0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Ah, missread. Let p=1, we found solutions. Let p=2, we found solutions, let p=3, .... $\endgroup$ – kelalaka Dec 8 '18 at 9:12
  • $\begingroup$ 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. $\endgroup$ – Ram_Giri Dec 8 '18 at 9:53
1
$\begingroup$

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

$\endgroup$

Your Answer

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

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