我們能用 mod m 找到給定餘數的確切數字嗎？

我有大約 1500 個號碼。號碼 $ x_i $ 計算為 $ x_i $ =( $ p*t_i $ ) 模米。 $ p $ 所有數字都保持不變且相同，而 $ t_i $ 每次都是隨機選擇的。例如給定的數字 $ x_i $ 的計算如下：

$ x_1 $ =( $ p*t_1 $ ) 模米。

$ x_2 $ =( $ p*t_2 $ ) 模米。

. . .

$ x_{1500} $ =( $ p*t_{1500} $ ) 模米。

給定 $ x_i $ ’s 和 m，我們能用上面的方法找到 p $ x_{i} $ 的？

如果你知道的話 $ m $ 和 $ x_i $ 但不是 $ t_i $ 那麼就沒有辦法找到 $ p $ 一般來說。例如，假設 $ m $ 是素數。那麼，對於任何 $ p \ne 0 $ , 有一組合適的 $ t_i $ , 由 $ t_i = p^{-1} x_i $ . 唯一的價值 $ p $ 這可能是不可能的 $ 0 $ , 只有當所有 $ x_i $ 為零。

更一般地說，您可以獲得的唯一資訊 $ p $ 是排除某些共同的因素 $ m $ . 如果 $ k $ 是一個因素 $ m $ 和 $ x_i $ 不是所有的倍數 $ k $ 然後 $ p $ 不能是的倍數 $ k $ 任何一個。這就是你所擁有的所有資訊 $ p $ .

（請注意，在這個答案中，我工作模 $ m $ ，所以例如當我寫 $ p \ne 0 $ 我是說 $ p \ne 0 \pmod m $ .)

引用自：https://crypto.stackexchange.com/questions/64660