如果 F := GF(p^n) 是具有 p^n 个元素的有限域，其中 p 是素数，n 是自然数，是否有任何有效的算法来计算 F 中两个元素的乘积？
到目前为止，这是我的想法:
我知道 F 的标准构造是在 GF(p) 中取 n 次不可约多项式 f，然后将 F 的元素视为商 GF(p)[X]/(f) 中的多项式，并且我有一种感觉，这可能已经是正确的方法，因为多项式乘法和加法应该很容易实现，但不知何故，我不知道如何实际做到这一点。例如，如何选择合适的 f，如何获得任意多项式的等价类？
最佳答案
首先选择 GF[p] 上的 n 次不可约多项式。只需生成随机的，随机多项式是 irreducible with probability ~1/n .
要测试随机多项式，您需要一些代码来对 GF[p] 上的多项式进行因式分解，请参阅 the wikipedia page对于某些算法。
那么 GF[p^n] 中的元素只是 GF[p] 上的 n 次多项式。只需进行正常的多项式算术，并确保计算不可约多项式的余数即可。
编写该方案的简单版本非常容易。您的实现方式可能会变得任意复杂，例如模运算。请参阅modular exponentiation , Montgomery multiplication ，并使用 FFT 进行乘法。
关于math - 如何在有限域中实现乘法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1935658/