Elliptic-Curves
為什麼橢圓曲線中的求逆和乘法運算成本很高？
有幾種算法可以有效地將任意點P(x,y)與定義的橢圓曲線中的某個正整數k進行標量相乘 $ F_{p} $ 或者 $ F_{2^{m}} $ .
標量乘法處理點加倍（將**P(x,y)**添加到自身）和點加法（添加兩個不同的點（P(x,y)， Q(X,Y)）。這些點加倍和加法，從根本上說，進一步處理加法、平方、乘法和求逆運算。
我這裡的問題是，雖然標量點乘法涉及相當多的加法和平方運算，（例如，單點加法需要8次加法，1次平方，2次乘法和1次反轉）為什麼反轉乘法比（I / M ) 對於標量點乘法的不同算法的性能評估，研究人員是否特別感興趣？
我確實知道在橢圓曲線算術中倒數和乘法運算占主導地位，但是這些加法和平方運算不是占主導地位嗎？
我鼓勵讀者仔細閱讀第 3.13 頁的表。145 在這 本書中，以便您可以清楚地了解我的問題。請查看此表中標題為“EC 操作”和“現場操作”的最後 2 列。
例如，當我們執行兩個橢圓曲線點的點加法時，我們需要處理定義橢圓曲線的場的元素。我們可能需要執行幾個操作，加點的總成本是我們需要做的所有現場操作成本的總和（加上一些成本，這通常很小）：
- 我們可能需要添加和減去欄位元素。兩種操作的成本大致相同，因此我們通常不區分它們。它們也很便宜（與所需的其他操作相比），因此在計算總成本的近似值時忽略它們是很常見的。
- 我們可能需要將兩個元素相乘。此操作的成本通常是衡量所有其他成本的“單位”。
- 我們可能需要對一個元素求平方。這可以通過將元素交給乘法常式來完成；然而，我們可以利用一些對稱性來降低這個特定操作的成本。對於奇數特徵場，此平方運算將介於乘法成本的 0.5 到 1 倍之間。不同的實現會在精確的數字上有所不同；我們試圖解釋這一點。
- 我們可能需要找到一個元素的乘法逆元；也就是說，給定 $ x $ ，求值 $ y $ 這樣 $ xy = 1 $ ， 在哪裡 $ 1 $ 是乘法恆等式。對於幾乎任何表示，此操作是迄今為止最昂貴的操作。
這個 $ I/M $ value 試圖準確捕捉逆運算的成本；一個 $ I/M $ 值 8 估計逆運算的成本大約與 8 次乘法運算的總和一樣昂貴。
我們需要在這裡進行估算，以指導我們哪種操作組合執行速度最快。如果我們有一個 $ I/M $ 5，然後用 6 個乘法替換一個逆的優化是損失。但是，如果我們有一個 $ I/M $ 值為 8；那麼這是一場胜利。
現在，根據我的經驗， $ I/M $ 比率往往相當高；8 的比率將遠遠小於我所看到的。