同餘問題的難度
問題描述如下。讓 $ c_1=p_1q_1+r $ , $ c_2=p_2q_2+r $ , $ \cdots $ , $ c_n=p_nq_n+r $ ， 在哪裡 $ p_i $ 的， $ q_i $ 的， $ r $ 都是大的正整數，並且 $ p_i $ ‘沙 $ q_i $ 是隨機選擇的。請注意 $ p_i $ ‘沙 $ q_i $ 是不同的，而 $ r $ 是一樣的。現在知道了 $ c_1,\cdots,c_n $ ，他知道上面的結構 $ c_1,\cdots,c_n $ ，但他不知道 $ p_i $ 的或 $ q_i $ 的。他的目標是提取價值 $ r $ 從 $ c_1,\cdots,c_n $ . 這個問題難嗎（要麼被證明是難的，要麼還沒有找到多項式求解算法）？這個問題有名字嗎？
一個類似（但更容易）的問題是求解線性同餘系統：通過知道 $ c_1,\cdots,c_n $ 和 $ p_1,\cdots,p_n $ ， 解決 $ r $ 從方程 $ r\equiv c_1\mod p_1 $ , $ r\equiv c_2\mod p_2 $ , $ \cdots $ , $ r\equiv c_n\mod p_n $ . 這個問題與中國剩餘定理有關，我知道它有多項式時間求解算法。但是，在我上面第一段的問題中，只有一個人知道 $ c_1,\cdots,c_n $ ，但不知道模數 $ p_1,\cdots,p_n $ （或者 $ q_1,\cdots,q_n $ ），我的問題可能更難。我只能找到關於線性同餘的作品，但找不到關於我的問題的相關作品。有人熟悉這個問題嗎？我只是想知道這是一個曾經研究過的問題。
結合 fgrieu 和我的觀察，似乎有一個很大的 $ r $ 給予足夠的可以恢復 $ p_iq_i + r $ 價值觀。
特別是，我們將假設兩者 $ p_i $ 和 $ q_i $ 被統一選擇。
然後， $ (p_iq_i + r) = r \pmod s $ 將保持至少的機率 $ (2s-1)/s^2 \approx 2/s $ （因為它會保持，如果 $ p_i $ 或者 $ q_i $ 為 0 模 $ s $ , $ (p_iq_i + r) \bmod s $ 將是任何其他特定值，機率約為 $ 1/s $ . 實際上，如果 $ s $ 是較小素數的冪，我們暫時忽略它。
因此，我們可以做的是，對於各種小素數 $ s $ ，拿我們的 $ p_iq_i + r $ 值，併計算 $ p_iq_i + r \bmod s $ ，並查看最常發生的值。這會給我們可能的價值 $ r \bmod s $ . 然後，我們取所有可能的值，並使用中國剩餘定理重構 $ r $ .
如果我們有 10,000 個這樣的值，我們可以使用最高 710 的素數；對於每個值 $ s $ , 的正確值 $ r \bmod s $ 將比其餘的至少有 3 個標準差（因此最常見的值可能是正確的），這將為我們提供足夠的關係來恢復 1024 位 $ r $ .
然後我們可以使用 fgrieu 的觀察來驗證 $ r $ 被覆蓋。