python - 在伽罗华域中生成反向元素

Question

我有伽罗华域 GF(2^409) 和不可约多项式f(x) = x^409 + x^15 + x^6 + x + 1 其中系数只能为 1 或 0

如果我有这个字段a(x)的一些元素，我如何找到反向元素a_1(x)，这样

a(x) * a_1(x) = 1 (mod f(x))

使用扩展欧克力德算法

• 我正在使用多项式基础

• 我知道我可以使用 pow(a(x),2^409 - 2) 找到 a_1(x)，但我使用Python，电源操作耗时太多

• 我在定义多项式下的除法运算时遇到了麻烦(没有它我不能使用扩展 Euklid 算法)

Answer 1

表示 GF(2^k) 元素的一种常见方法是使用大整数(Python 2 中的long，int in Python 3) 并让每一位代表一个系数。要执行多项式除法，您基本上可以按照使用笔和纸执行长除法的步骤进行操作。

让我们举一些更简单的例子。以 GF(2⁷) 为模 x⁷ + x + 1。让我们尝试求 x⁶ + x ^的倒数3 + x。因此，您必须使用扩展欧几里得算法计算这两个多项式的 GCD。第一步是计算一个的商和余数。即度数大的除以度数小的。

x⁶ + x³ + x 是 1x⁶ + 0x⁵ + 0x⁴ + 1x³ + 0x² + 1x¹ + 0x⁰ 或 1 0 0 1 0 1 0 简而言之。按照相同的约定，模数为 1 0 0 0 0 0 1 1。所以你分

1 0 0 0 0 0 1 1 / 1 0 0 1 0 1 0 = 1 0 remainder 1 0 1 1 1
1 0 0 1 0 1 0
      1 0 1 1 1

那我在这里做了什么？将 a 除以 b 我在每一个中寻找最高的集合位，即多项式的次数。这些度数之间的差异有点我想在商中设置。在这种情况下，a 的阶数为 7，b 的阶数为 6。差值为 1，因此商必须有项 x¹。现在我写下 b 乘以那个项，在这种情况下，它只是 b 的二进制表示向左移动了度数的差异)。然后我从原始 a 中减去该移位值，但我在 𝔽₂[x] 中进行减法，所以它实际上是一个 XOR 运算。其结果是一个新数字，我在下一次迭代中将其用作 a 的值。我继续，直到程度的差异变为负数，即我将较小程度的多项式除以较大程度的多项式。然后我就完成了，a 的最后一个值就是我的余数。在上面的划分中，一步完成。

通过执行除法余数的操作，您应该能够弄清楚欧几里德算法。扩展版本需要更多的工作，但请尝试一下。最后，你应该能发现，在上面给出的例子中，倒数是x³ + x + 1(由Sage计算)。为了比较，原始字段 GF(2⁴⁰⁹) 中 x⁶ + x³ + x 的倒数将是

"+".join("x^{}".format(i) for i in range(409,-1,-1) if (1 << i) & 71418312917235914488287388787154746126088900129923309868417397199063993100653429184865046255190862140902867842544110449930)

我在 Sage 中计算的这个数字:

x = polygen(ZZ)
m = x^ 409 + x^15 + x^6 + x + 1
F409 = GF(2^409, name="z", modulus=p)
z = F409.gen()
(1/(z^6+z^3+z)).polynomial().change_ring(ZZ)(2)