Itoh Tsuji算法

Question

我想对动态替换表使用伊藤-津吉算法，但我没有得到以下行：r\ \gets\ (p^m - 1)\,/\,(p - 1)

为什么r可以在包含p^m元素的伽罗瓦域中通过在场GF(p)中计算它来计算一个数的乘积逆，并利用这个结果来计算GF(p^m)场中的反演？

Answer 1

我最近详细介绍了在关于曲线9767的文章中使用Itoh(第3.6节)。

在下面的描述中，我将GF(p^m)的元素写成多项式，在GF(p)[z]中取模一个给定的不可约酉多项式M (由于所有具有相同基数的有限域都是同构的，所以特定M的选择对安全性没有重要意义，但是M的一些选择可以提高性能，如下所示)。我们考虑了计算给定元素a^{-1}的逆a \in GF(p^m)问题( a \neq 0)。

• p^m-1是p-1的倍数；实际上，商数是：r = \frac{p^m-1}{p-1} = 1 + p + p^2 + p^3 + \cdots + p^{m-1}
• 对于与零不同的任何a \in GF(p^m)，我们可以将a的逆表示为：a^{-1} = \frac{a^{r-1}}{a^r} 对于任何整数r都是正确的，但是对于r = (p^m-1)/(p-1)，这会导致快速反演，这要归功于以下两个主要事实。
• Fact 1: a^r \in GF(p)。实际上，(a^r)^{p-1} = a^{p^m-1} = 1 (因为p^m-1是GF(p^m)中可逆元素组的顺序)。因此，a^r是多项式方程X^{p-1} - 1 = 0的根。然而，GF(p)的所有非零元素都是该多项式的根( 费马小定理)，而GF(p)中有p-1非零元素，而X^{p-1} - 1是字段中的度p-1多项式，不能超过p-1根。因此，X^{p-1}-1的根就是GF(p)的非零元素，a^r就是其中之一。这意味着倒置a^r比在一般情况下反演GF(p^m)元素要容易得多，因为我们可以在GF(p)中工作。计算逆模p的方法有很多种，但如果p是小的，费马的小定理就能很好地工作(即把a^r提高到幂p-2)。
• Fact 2:计算a^{r-1}很便宜，这要归功于Frobenius自同构。j-th Frobenius自同构( j >= 0)是：\begin{eqnarray*} \Phi_j : GF(p^m) &\longrightarrow& GF(p^m) \\ a &\longmapsto& a^{p^j} \end{eqnarray*}，即\Phi_1只是“提升到幂p"，\Phi_j是”应用\Phi_1精确j时间“。该运算符是字段自同构：\Phi_j(ab) = \Phi_j(a) \Phi_j(b)和\Phi_j(a+b) = \Phi_j(a) + \Phi_j(b)，用于所有a, b \in GF(p^m)。这使得它是线性的(如果我们将GF(p^m)解释为GF(p)上维数m的向量空间)，因此计算起来相当容易: if：a = \sum_{i=0}^{m-1} a_i z^i 然后：\Phi_j(x) = \sum_{i=0}^{m-1} a_i \Phi_j(z^i) ，而且，如果GF(p^m)是用某种常量c \in GF(p)的形式M = z^m - c的模数来定义的(有常数c确保z^m-c是不可约的，只要m划分p-1)，那么\Phi_j(z^i) = c^{ij(p-1)/m}，而将\Phi_j应用于任何值a就变成了将a的m系数a_i乘以易于预先计算的m常数的问题。这使得\Phi_j便宜(比GF(p^m)中的一次乘法便宜得多)。对于任何a \in GF(p^m)，我们都可以用几个乘法和Frobenius算子来计算a^{r-1}：有关于\log m乘法的\begin{eqnarray*} t_1 &=& \Phi_1(a) &=& a^{p} \\ t_2 &=& t_1 \Phi_1(t_1) &=& a^{p+p^2} \\ t_3 &=& t_2 \Phi_2(t_2) &=& a^{p+p^2+p^3+p^4} \\ t_4 &=& t_3 \Phi_4(t_3) &=& a^{p+p^2+p^3+p^4+\cdots+p^{8}} \\ & & \ldots & & \end{eqnarray*}和Frobenius算子的应用，就可以得到a^{r-1}。

然后，利用上述所有这些，a \in GF(p^m)的完整反演算法如下：

1. 利用乘法和Frobenius算子计算a^{r-1}。
2. 用a乘以a^{r-1}，得到a^r (这个乘法很容易，因为我们知道结果在GF(p)中，所以我们只需要计算一个系数；其他的系数都是零)。
3. 在a^r中反演GF(p) (例如使用Fermat的小定理)。
4. 将a^{r-1}乘以a^{-r} (这种乘法也很容易，因为a^{-r} \in GF(p))。

在使用场Curve9767 GF(9767^{19})的情况下，我可以得到反演的全部成本，大约是GF(p^m)乘法的6到7.7倍，它足够快，可以认真考虑使用仿射坐标在椭圆曲线上的运算。通过比较，通常的逆模算法--256位整数n --其开销将是乘法模n的50到300倍。

所有这些都是在GF(p^m)的泛型上下文中提到的。Itoh和Tsuji首先将其描述为GF(2^m)，即使用p = 2，在这种情况下，Frobenius算子\Phi_1只是“平方”。此外，对于p = 2，GF(p)中的反演是一个非操作(因为GF(2)只有一个非零元素，即1，而1是它自己的逆)，所以a^r = 1；a^r的反转和a^{-r}的乘法可以跳过。另一方面，对于p = 2，对于某些c \in GF(2)，模M不能是z^m-c，因为X^m和X^m-1在GF(2)上都不是不可约的，需要一个不可约模才能得到一个域。这使得Frobenius运算符计算起来有点复杂(但仍然相当有效)。