Rsa
計算複雜性：ECC 乘法與模乘法
在橢圓曲線上執行標量乘法與在以素數為模的乘法群中取冪有何不同？
即在給定大小的橢圓曲線上 $ |t| $ ，計算的複雜度是多少 $ kP $ 關於 $ |k| $ 和 $ |t| $ ?
相比之下，形式的模冪運算的計算複雜度是多少 $ g^a \bmod p $ 關於 $ |g|=|p| $ 和 $ |a| $ ?
分別知道雙加和平方乘的答案已經是一個很大的幫助。
如果您只關心計算複雜度，則類似：
- 在 ECC 中：雙加步驟的數量與 $ O(|k|) $ （每一位加一倍，每一位加一 $ 1 $ 位，在非視窗算法中）。每個雙精度/加法是一個恆定數量的欄位乘法、平方、加法和減法的序列。乘法和平方是昂貴的，使用 Karatsuba 算法，它們是 $ O(|t|^{1.58} $ ）。因此結果是 $ O(|k||t|^{1.58}) $ .
- 模冪也是一樣的。平方和乘法是 $ O(|a|) $ . 每個平方/乘法是 $ O(|p|^{1.58} $ ）。因此結果是 $ O(|a||p|^{1.58} $ )
當然，如果您需要更精確，則必須決定特定的點乘法/模冪運算算法，因為有些算法使用視窗和預計算表；在 ECC 中，還有加點和加倍的特定公式。