是否有關於“模組化近似最大除數”問題的任何資訊？
近似最大公約數(AGCD) 問題是獲取值的難度 $ \ p\ $ 當給定樣本時 $ \ pq_i + e_i $ 對於秘密值 $ p, q_i, e_i $ .
我想知道當合併模組化減少時問題的難度如何變化。
具體來說：是獲取的問題 $ \ p\ $ 從樣品 $ \ pq_i + e_i \bmod x $ 有秘密 $ \ p, q_i, e_i $ 和公開的 $ x $ 與前面提到的整數運算問題變體的硬度相等嗎？
在搜尋術語“模組化 AGCD”時，我找不到有關此版本問題的資訊，但我不知道該將其稱為什麼。兩者之間的差異可能可以忽略不計，不能保證將其分類為單獨的問題，但我不確定。直覺地說，具有模數的變體似乎更難解決。但我想要關於任何差異的定量細節，如果有的話。
編輯
Poncho 的回答強調了參數的大小在討論問題的難度時很重要。我對以下參數大小的問題感興趣：
$ x $ 是 1792 位素數
$ p $ 是一個均勻隨機的 1792 位整數
每個 $ q_i $ 是一個 1536 位整數，其中 1280 個最高有效位均勻隨機
- 接下來的低 255 位設置為 0，最低有效位設置為 1
每個 $ e_i $ 是一個 1024 位的隨機整數
具體來說：是獲取的問題 $ \ p\ $ 從樣品 $ \ pq_i + e_i \bmod x $ 有秘密 $ \ p, q_i, e_i $ 和公開的 $ x $ 與前面提到的整數運算問題變體的硬度相等嗎？
實際上，如果 $ p $ 相對質數 $ x $ , 和 $ q_i $ 值均勻分佈在 $ [0, x-1] $ ，那麼它比 AGCD 問題更難，因為它是資訊安全的（而不是計算安全的），也就是說，即使我們假設攻擊者俱有無限的計算能力，他仍然無法恢復 $ p $ .
展示實際上相當簡單；即使我們假設攻擊者知道 $ e_i $ ，然後對於任何樣本值 $ s = pq_i + e_i \bmod x $ , 對於任何潛在價值 $ p’ $ , 存在唯一的 $ q’_i $ 值，即 $ p’^{-1}(s - e_i) \bmod x $ 這將產生觀察到的樣本 $ s $ ，因此攻擊者沒有獲得任何候選值的相對機率的資訊 $ p $ （除了它是否相對質數 $ x $ )
我的直覺是不會。假設我們有一個模組化 AGCD 的高效求解器，我們稱之為 $ \mathcal{A} $ . 給定一些樣本 $ p_1, p_2, … p_j $ 和 $ p_i = pq_i + e_i \bmod{x} $ 我們可以用 $ \mathcal{A}(p_1, p_2, … p_j, x) $ 恢復 $ p $ .
這意味著 AGCD 有一個有效的求解器，我們稱之為 $ \mathcal{B} $ . 我們可以構造 $ \mathcal{B} $ 從 $ \mathcal{A} $ . 給定一些樣本 $ p_1, p_2, … p_x $ 和 $ p_i = pq_i + e_i $ 我們可以定義 $ \mathcal{B}(p_1, p_2, … p_j) $ 作為：
- 隨機抽樣一個隨機素數 $ x $
- 利用 $ \mathcal{A}(p_1, p_2, … p_i, x) $ 給我們 $ p \bmod{x} $ .
- 用不同的方法重複步驟 1 和 2 $ x $ , 然後使用 CRT 將同餘組合起來恢復 $ p $ .
如果我們假設 AGCD 沒有有效的求解器 $ \mathcal{B} $ ，那麼這意味著不可能有有效的求解器 $ \mathcal{A} $ 對於模組化 AGCD（因為 $ \mathcal{A} $ 可以用來簡單地構造 $ \mathcal{B} $ ）。這意味著模組化 AGCD 至少與 AGCD 一樣難。