如何計算 ElGamal 密碼系統的複雜度？

ElGamal加密和解密的時間和空間複雜度如何計算，因為加密期間有兩次冪運算，解密期間有一次？這是我的加密程式碼：

for i=1:d 
   pow=pow*g;
   y=pow%p;
for j=1:r
   pow1=pow1*g;
   C1=pow1*g;
   pow2=pow2*y;
   C2=(M*pow2)%p;

我認為第一個 for 循環將執行 $ O(d) $ 次和第二次 for 循環將執行 $ O(r) $ 所以總時間複雜度是 $ O(d)+O(r) $ 因為不知道哪個更大 $ r $ 和 $ d $ .

好吧，您的程式碼存在一些主要問題。從技術上講，您的程式碼的時間估計是正確的（也就是說，如果您在更新 pow1 和 pow2 時插入模運算），但是實際上沒有人會使用該算法來執行 ElGamal。

讓我們解決一些問題：

• 你使用一個 $ O(N) $ 計算算法 $ x^N $ ; 在實際使用中，指數很大（可能在 $ 2^{256} $ )，以及一個算法 $ O(2^{256}) $ 迭代是完全不可行的。在實踐中，我們使用的算法在 $ O(\log N) $ 運算（模乘法），例如這個；這將工作量減少到可以在實踐中實施的程度。
• 在不那麼激烈但仍然存在的問題上：您的程式碼似乎假設您擁有私鑰 $ d $ 加密時；在實踐中，您將從公鑰開始（我相信您的程式碼是 $ y $ .
• 此外，當我列出 nits 時，您還需要在計算 C1 時執行模組化歸約。此外，您不需要在循環中重新計算 C1 和 C2；您只對最終值感興趣，因此您可以在獲得 pow1 和 pow2 的最終值後計算它們。

我確定還有其他我錯過的問題。然而，底線是，如果你真的想計算 ElGamal 的時間複雜度，你需要使用我們在實踐中實際實現的算法。

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