更一般的 - 從 r*p mod q 中恢復 r 的難題是什麼？
我想知道與恢復整數關係最密切的密碼學難題 $ r $ 從模組化產品 $ r\times p\mod q $ . （這是對先前有一些錯誤的文章的簡化）。在我看來，它真的像整數分解；如果不是，還會是什麼？
更具體地說，選擇兩個素數 $ p $ 和 $ q $ , $ q>p $ , 和一個隨機正整數 $ r $ , 足夠大使得 $ q/p<r<q $ . 發布 $ q $ , 但保持 $ p $ 和 $ r $ 私人的。此外，假設有幾個實例 $ r $ 對於給定的一對 $ \langle p, q\rangle $ 跟…共事。假設存在一個硬度問題 X，這樣 X 的多項式時間解可以簡化為找到 $ r $ 或者 $ p $ 從整數
$$ r\times p\mod q $$在多項式時間內，這個問題 X 是什麼？ 我對此比較陌生。我看了幾個難題；似乎沒有任何殘留性或離散對數問題適用，但我很猶豫說它是整數分解或 RSA，以防出現更適合的更強假設的問題。我想對構造進行良好的表徵，以便我可以準確地描述它。
感謝您的幫助和耐心！
當給定一個由以下組成的三元組時 $ (p,q,x) $ 和 $ x = r \cdot p \mod q $ ，則不存在硬問題。計算需要一次求逆和一次乘法（均在模算術中） $ r $ .
如果只是 $ x $ 給出，那麼你可以選擇 $ p $ 和 $ q $ 任意計算匹配 $ r $ 填滿 $ x = rp \mod q $ .
如果實際問題是關於恢復原始值：那是不可能的。這與只為隨機值提供一些界限的情況完全相同（例如 $ q>x $ )，僅此而已。
在目前陳述的問題中， $ p $ 和 $ q $ 是素數 $ p $ 秘密和 $ q $ 已知， $ p<q $ ，它是隨機選擇的（我假設：統一） $ r_i $ 和 $ q/p<r_i<q $ ，並揭示 $ x_i=X(r_i)=r_i\times p\bmod q $ . 問題是發現 $ p $ （或以其他方式找到一些 $ r_i $ , 這在實踐中會導致 $ p $ ).
如果我們替換選擇 $ r_i $ 經過 $ 0<r_i<q $ ，那麼這個問題顯然是難以解決的，因為 $ X $ 是集合的映射 $ {1,2,\dots,q-1} $ , 因此分佈 $ x_i $ 無論如何都是均勻隨機的 $ p $ 是。
如果 $ q/p<2 $ ， 然後 $ r_i=1 $ 不可能發生（因為 $ p $ 不分 $ q $ ）。因此， $ p $ 不能是其中之一 $ x_i $ 之中 $ {1,2,\dots,q-1} $ ，問題就變成了尋找缺失值 $ p $ . 必要數量 $ x_i $ 與經過充分研究的優惠券收集者的問題有關，並且可以確定 $ p $ 需要 $ O(q\log(q)) $ 的值 $ x_i $ , 並且對於大 $ q $ .
更一般地說，我們只能確定 $ p $ 當我們發現 $ x_i $ 達到了除其中之一之外的所有 $ q-\lfloor q/p\rfloor $ 值，並且問題是難以解決的，除非兩者都 $ p $ 和 $ q $ 很小。
據我所知，這不是一個經過充分研究的問題。它與整數分解問題或離散對數問題無關，兩者的輸入都相對較小，而這裡的輸入包含大量 $ x_i $ .