我需要將硬背包轉換為超增量背包。

我有這些超增量值（3,6,11,22,43,87）。我也有 w = 7 和 n = 173。我通過計算將超增量值轉換為硬值 (21,42,77,154,128,90) $ a_i = x_i * w \bmod{n} $ .

(3 * 7) mod 173 = 21
(6 * 7) mod 173 = 42
(11 * 7) mod 173 = 77
(22 * 7) mod 173 = 154
(43 * 7) mod 173 = 128
(87 * 7) mod 173 = 90

問題

我想問如果我有硬值，我怎樣才能獲得超值。

例子

我可以將 (21,42,77,154,128,90) 轉換為 (3,6,11,22,43,87) 嗎 $ w = 7 $ 和 $ n = 173 $ ? 或者如果 w = 7 且 n = 173，我如何找到 x_i？

(x1 * w) mod n = 21
(x2 * w) mod n = 42
(x3 * w) mod n = 77
(x4 * w) mod n = 154
(x5 * w) mod n = 128
(x6 * w) mod n = 90

想法是這樣的：給定 $ w $ 和 $ n $ , 我們找到一個數 $ v $ 這樣 $ vw \equiv 1 \pmod{n} $ . 在你的情況下 $ w=7 $ 和 $ n=173 $ ， 我們有 $ v=99 $ ; 這樣一個 $ v $ 將永遠存在，如果 $ w $ 和 $ n $ 是互質的，可以通過擴展歐幾里得算法求出。價值 $ v $ 允許我們從“硬值”映射到“超增長值”。

下面是它的工作原理，假設有人想向您發送與第一、第三和第五個索引相對應的消息：為了加密它，他獲取公鑰，查找第一、第三和第五個索引並添加它們 $ 21 + 77 + 128 = 226 $ ; 他發送值 $ 226 $ 作為密文。

你（私鑰的持有者）要做的就是將密文（226）乘以 $ v $ 模組 $ n $ ; 這給了 $ 226 \times 99 \equiv 57 \pmod{173} $ . 然後你通過原始的超增列表來解碼，很容易看到 $ 57 = 43 + 11 + 3 $ ; 即第一、第三和第五個指標，正確解碼消息。

這種解碼方法效果很好——這個加密系統的問題是它可以被破解；本文展示了攻擊者如何在沒有私鑰的情況下快速解碼。

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