密码学 ｜ 6.3.1 二重加法算法

注：在计算  的时候还有一个额外的技巧可以稍微减少计算时间。基础想法是将  表示为 2 的幂次和与差，这样操作能够减少项数，在计算  的时候只用加更少的点。而一个重要的关键是在椭圆曲线中，减去一个点和加上一个点是一样容易的，因为 。这和在  中可相差甚远，因为在  下计算  需要的操作比计算两个元素相乘要麻烦的多。

举个例子，就拿例 6.16 中的  来说，，计算  一共需要 15 次“点加”（9次加倍，6次加法）但是如果我们把 947 表示为

那么我们可以计算

只需要 10 次加倍和 4 次加法总共 14 次”点加“。将一个数展开为正的 2 幂次和负的 2 幂次之和的技术称为 n 的 3 元展开。

这样的技术能够节省多少操作呢？假设  是一个很大的数，我们设 ，在极端的情况下 ，那么使用二元展开的  计算  需要  次“点加”（ 次加倍和  次加法），因为

但是如果我们使用 3 元展开，我们在接下来会证明（命题 6.18）计算  只需要不超过  次“点加” （ 次加倍和  次加法）

上面考虑的是最极端的情况，但我们也需要知道平均情况下其表现如何。对一个随机数进行二元展开那么大约会有同样数量的 0 和 1，所以对于大多数的 ，通过二元展开计算  大约需要  次“点加” （ 次加倍和  次加法）。但是如果我们使用 3 元展开，可以测试的是大多数  展开后有  的项是 0，所以计算  大约只需要  次“点加” （ 次加倍和  次加法）

(6.6)2s+ss+1+⋯+2s+t−1+0⋅2s+t