計算平方根的算法高飛_(2n)GF(2n)GF(2^n)

簡短的問題：是否有一種算法可以有效地計算平方根 $ \mathbb{F}_{2^n} $ ?

是的，有一種算法可以有效地計算平方根 $ GF(2^n) $ .

我不知道這是否是最有效的已知算法，但是可以通過觀察內部的平方來證明有效算法的存在 $ GF(2^n) $ 是按位線性運算，因此它等效於取值的位表示，並將其乘以 $ n\times n $ 矩陣 $ GF(2) $ 以獲得序列的位表示。因此，可以通過計算逆矩陣並乘以它來求逆。

此外，您已使用“quadratic-residuosity”標籤標記了問題；然而該領域 $ GF(2^n) $ 具有所有元素都是二次餘數的特殊性質；也就是說，對於任何元素 $ x $ , 會有一個獨特的元素 $ y $ 和 $ y^2 = x $ . 因此，在這個領域，二次剩餘性問題是無趣的。

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