日期:
来源:山石网科安全技术研究院收集编辑:V
注:在计算 的时候还有一个额外的技巧可以稍微减少计算时间。基础想法是将 表示为 2 的幂次和与差,这样操作能够减少项数,在计算 的时候只用加更少的点。而一个重要的关键是在椭圆曲线中,减去一个点和加上一个点是一样容易的,因为 。这和在 中可相差甚远,因为在 下计算 需要的操作比计算两个元素相乘要麻烦的多。
举个例子,就拿例 6.16 中的 来说,,计算 一共需要 15 次“点加”(9次加倍,6次加法)但是如果我们把 947 表示为
那么我们可以计算
只需要 10 次加倍和 4 次加法总共 14 次”点加“。将一个数展开为正的 2 幂次和负的 2 幂次之和的技术称为 n 的 3 元展开。
这样的技术能够节省多少操作呢?假设 是一个很大的数,我们设 ,在极端的情况下 ,那么使用二元展开的 计算 需要 次“点加”( 次加倍和 次加法),因为
但是如果我们使用 3 元展开,我们在接下来会证明(命题 6.18)计算 只需要不超过 次“点加” ( 次加倍和 次加法)
上面考虑的是最极端的情况,但我们也需要知道平均情况下其表现如何。对一个随机数进行二元展开那么大约会有同样数量的 0 和 1,所以对于大多数的 ,通过二元展开计算 大约需要 次“点加” ( 次加倍和 次加法)。但是如果我们使用 3 元展开,可以测试的是大多数 展开后有 的项是 0,所以计算 大约只需要 次“点加” ( 次加倍和 次加法)