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 ?

Improve this question
$\endgroup$
2
  • $\begingroup$ Ah, missread. Let p=1, we found solutions. Let p=2, we found solutions, let p=3, .... $\endgroup$
    – kelalaka
    Commented Dec 8, 2018 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
    Commented Dec 8, 2018 at 9:53

1 Answer 1

Reset to default
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$.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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