在有限域上求单位的第n根

Question

我试图在有限域中找到统一的n-th根，这是给我的。n是2的幂，有限域具有素数阶。我知道，如果这只是正常的数字，我可以用e^{(2\pi ik/n)}找到它。我不知道如何将其转化为有限域。

Answer 1

在大小为q的有限域中，乘法子群具有阶q-1 (即除0外所有元素都是可逆的)。如果n相对于q-1是素的，那么只有一个n-th的统一根，即1本身。如果n将q-1分割开来，那么就有了统一的n根。在这个答案的其余部分，我假设您在这种情况下，即n除以q-1。

下面所写的所有内容都使用有限字段中的计算(即模q，如果q是素数的话)。

要获得一个统一的n-th根，您可以在字段中生成一个随机的非零x。然后：

(x^{(q-1)/n})^n = x^{q-1} = 1

因此，x^{(q-1)/n}是一个统一的n-th根。请注意，您可以得到任何n-th的统一根(包括1本身)，每个根都有概率1/n。

现在，您可能希望有一个元n-th的单位根，即一个值g，这样可以通过整数j的值g^j (从0到n-1 )获得统一的所有n-th根。如果g是一个n-th的统一根，那么它是原始的当且仅当除n本身之外，任何将n分开的j > 0都是g^j \neq 1。在您的例子中，这很简单:因为n是2的一个强大功能，任何将n分隔开来的j也都是2的强大力量。在实践中，这会产生以下结果：

• 在有限域中得到一个随机x \neq 0。
• 计算g = x^{(q-1)/n}。
• 如果是g^{n/2} \neq 1，那么g是一个原始的n-th的统一根。否则，重新启动另一个随机x。

这将在每次迭代中成功地使用概率1/2，因此您将很快得到原始根。此外，这里不需要一个非常安全的随机生成器(除非选择原始根是某个秘密的一部分)。

注意，有几个原始的n-th根是统一的；在您的例子中，正是它们的n/2。他们中没有一个比其他人更原始，因此，没有“原始根”的概念。你找到了一个原始的根。