如果 F := GF(p^n) 是具有 p^n 个元素的有限域，其中 p 是素数和 na 个自然数，是否有任何有效的算法来计算 F 中两个元素的乘积？
到目前为止，这是我的想法：
我知道 F 的标准构造是在 GF(p) 中取 n 次不可约多项式 f，然后将 F 的元素视为商 GF(p)[X]/(f) 中的多项式，我有感觉这可能已经是正确的方法，因为多项式乘法和加法应该很容易实现，但我不知何故看不到这实际上是如何完成的。例如，如何选择合适的 f，以及如何获得任意多项式的等价类？
首先选择 GF[p] 上的 n 次不可约多项式。只需生成随机多项式，随机多项式不可约概率为 ~1/n。
要测试随机多项式，您需要一些代码来对 GF[p] 上的多项式进行因式分解，请参阅维基百科页面了解一些算法。
那么 GF[p^n] 中的元素只是 GF[p] 上的 n 次多项式。只需进行正常的多项式算术，并确保计算不可约多项式的余数。
编写该方案的简单版本非常容易。您的实现方式可能会变得任意复杂，例如模运算。请参阅模幂、蒙哥马利乘法和使用 FFT 的乘法。