用於伽羅瓦域

快速指數我希望能夠計算用於伽羅瓦域

g^x = g * g * g * ... * g  (x times)

其中g是在有限域GF（2^M）。這裏m相當大，m = 256,384,512等，所以查找表不是解決方案。我知道對於類似的想法有很快的算法，用於Z/nZ的modpow（請參閱第619-620頁的HAC）。

什麼是計算週期（即g^x）的快速非表格式方法？
這絕對是一個一廂情願的問題，但在這裏：montgomery multiplication/exponentiation的想法是否可以「回收」到伽羅瓦領域？我想這樣認爲是因爲同構性質，但我真的不知道。

備註：這是從我的post上math.stackoverflow.com我想這是最好的社區來問這個問題。

2012-07-24 torrho

喬楚建議多項式，每步後減少;這對我來說聽起來很公平。你有寫入多項式乘法嗎？如何減少？ – sarnold 2012-07-24 03:48:22

我目前沒有寫任何東西。從以前編碼Z/nZ modpow的經驗來看，我有一種預感，即在每一步之後減少的速度似乎很慢。我認爲必須有某種方法來避免這樣做的迭代（遞歸）方法，因爲它可以在Z/nZ中使用蒙哥馬利求冪的等價設置完成。 – torrho 2012-07-24 03:54:51

來自math stackexchange社區，我有兩個人建議Binary Exponentiaion。維基百科聲明遞歸它作爲遞歸算法。它可以改變爲一個迭代算法，如Wiki的僞代碼所示。

我對這個想法起初不以爲意，但是我更仔細地研究了它，並且發現了兩篇論文（1,2），它們可以幫助實現使用蒙哥馬利乘法的伽羅瓦域的二進制指數運算。

此外，Jyrki Lahtonen建議使用正常鹼基（或當m =/= 256,384,512等最佳正常鹼基）加速乘法。這種乘法方法可以在這個paper中找到。

感謝sarnold爲他/她的輸入。

2012-07-24 22:33:19 torrho

回答