第二十五个知识点：使用特殊的素数定义$GF(p)$和$GF(2^n)$的方法。

在我们之前看到的博客中，当实现密码学方案时，一个最频繁调用的操作就是模运算。不幸的是，尽管模块化的使用非常广泛，但是它不能像其它算术运算（如加法和乘法）那样容易的执行。蒙哥马利表达提供了一种解决方案，这里我们讨论另一种解决方法——伪梅森素数规约。

定义：如果一个素数$p$被写成如下形式，那么就称$p$位伪梅森素数。其中$b=2,c=1$时就是梅森素数。

\[P = b^n-c,其中0<|c|<2^{n/2} \]

实际上，$b$总是2，我们选择$c$通常是32位或者64位。

通过定义很容易推导出

\[p \equiv b^n-c \equiv 0 \mod p \\ b^n \equiv c \mod p \]

因此给定一个$k$位的整数$z$，我们让$z^{'}$为最低$n$位有效位，$z^{''}$是高$k-n$位有效位,就有$z = z^{''}2^n+z^{'}$，然后我们能重写$z \mod p$为

\[z \equiv z^{''}b^n+z{'} \equiv z^{''}c+z{'} \mod p \]

重复的计算上述式子，就可以得到$z \mod p$的值，这个值在$Z_p$中。($Z_p$就是模$p$的完全剩余系。)

下面有些需要注意的点：

1.$z^{'}$和$z^{''}$都能够通过简单的移位运算获得。

2.因为$c$被选择是一个字的长度，那么乘法计算会变得容易。

3.每次迭代会减少$k$的值。得到的值会是$max(k-n+w,n)$。

因此一般来说，计算伪梅森素数的约减将会仅仅需要移位，加法和乘法。

然而，使用这种方法的缺点也很明显，因为这种实现通常需要多方使用固定的设置，这可能会导致互操作性和安全性问题。更多的细节参考[1]和[2]。

$GF(2^n)$是另外一个经常被用到的域。

三项式和五项式是这个领域中最长用到的模。我们将会展示三项式如果简化约减。相同的技术亦可以直接用于五项式。

这个想法和素数域的那个非常类似。假设我们有三项式$f(x) = x^n+x^t+1$，其中 $ 0<t<n/2 $。

我们立刻就有

\[x^n \equiv x^t +1 \mod f(x) \]

给定多项式$z(x)$的次数大于$n$。我们把$z(n)$写成

\[z(x) = z^{''}(x)x^n+z{'}(x) \]

其中，$z^{'}(x)$是$z(x)$的最低$n$位，$z^{''}(x)$是剩下的位数。

然后我们就像在GF(p)中那样，我们计算模数通过：

\[z(x) \equiv z^{''}(x)x^n+z^{'}(x) \equiv z^{''}(x)(x^t+1)+z^{'}(x) \\ \equiv z^{''}(x)x^t+z^{''}(x)+z^{'}(x) \mod f(x) \]

这个运算因为$t$是一个更小的数使得它变得简单了。

[2]中也描述了标准规约的另一个优化。考虑到标准的例程会规约$z(x)$ 的次数$m$而不是$f(x)$的次数$n$：

\[z(x) = a_mx^m+a_{m-1}x^{m-1}+...+a_1x^1+a_0x^0 \\ f(x) = x^n+x^t+1 \]

当我们尝试规约$a_ix^i$，有下面两种情况：

因为添加$0$不会改变余数，这两种情况可以被一般化，因此我们能写下如下的标准规约程序：

Input:$z(x)$

Output:$z(x)$

1.for $i=m$ to $n$ by -1

2.{

3.$a_{i-n+t}+=a_i$

4.$a_{i-n}+=a_i$

5.}

使用这样算法的在软件上的优化不是明显的。但是在硬件上的优化是明显的，同时仅仅更新了$z(x)$，不需要额外的存储。

另外一个优点就是这样的形式仅仅需要$ 0<t<n $，它能被在常量时间内执行。

[1]Menezes, Alfred J., Paul C. Van Oorschot, and Scott A. Vanstone. Handbook of applied cryptography. CRC press, 1996.

[2]Blake, Ian F., Gadiel Seroussi, and Nigel Smart. Elliptic curves in cryptography. Vol. 265. Cambridge university press, 1999.

第二十五个知识点：使用特殊的素数定义\(GF(p)\)和\(GF(2^n)\)的方法。