檢索具有負指數值的 ElGamal 消息
儘管 ElGamal 方案聲明消息 $ M $ 一定是 $ 1 \le M \le p-1 $ 在本文中：A Secure and Optimally Efficient Multi-Authority Election Scheme他們提出了一種方法，其中消息可以 $ -l \le M \le l $ 在哪裡 $ |\ l\ | \lt p/2 $ . 這在第 9 頁中有說明。
論文背後的想法是，對於 2 路投票系統，可用選項編碼為 $ m_0=1,\ m_1=-1 $ 在進行加法 ElGamal 時，結果可能是 $ g^{-4} $ 或任何負指數。
我知道為了在 ElGamal 的最後階段計算消息，我們為每個可能的值執行一個循環 $ M $ 但在這種情況下，雖然這也是論文提出的，但我不明白它是如何完成的。
為了檢索消息 $ M $ 從 ElGamal 的最後一步提供的離散日誌中，知道 $ -l \le M \le l \text{ where } |\ l\ | \lt \lfloor p/2\rfloor $ 工作方式就像 $ 1 \le M \le p - 1 $ 也就是說，測試所有指數。對於負值 $ l $ 我們使用模組化除法，例如$$ 5^{-3} \equiv 125^{-1} \equiv 6^{-1} \equiv 6\bmod7 $$我們用 Ext-GCD 算法求逆
需要注意的是 $ |\ l\ | \lt p/2 $ 在哪裡 $ p/2 $ 向下**舍入，**例如 $ l=5 $ 然後 $ p \ge 13 $ . 原因是編碼值的數量 $ -l \le M \le l $ 是 $ 2\ l + 1 $ 由於值的存在 $ 0 $ 並且定義的循環組必須具有大於此的順序。