ECC:多重乘法逆的应用

Question

最近，我在蒙哥马利技巧在标量乘法中的应用上读到了Palash和Palash的"Montgomery技巧“，它提供了一种使用这种技术同时计算多个乘法逆的方法：

if x = 1/(ab), then 1/a = xb and 1/b = xa

我还分析了用Laszlo在无乘法模逆算法上计算乘法逆的各种算法。

在第12页的顶部，他们简短地提到：

但是，在椭圆曲线密码学中，最简单的(仿射)点表示和点加法的实现是最好的(射影、Jacobian和Chudnovsky-Jacobian坐标比较慢，参见8)。T

当然，射影坐标通常使用延迟逆，但每点相加的乘法更多。

仿射坐标所需的运算较少，但反求是在每一点加法时进行，而不是在结束时计算一次。

据我所知，Montgomery技巧可以消除每一步的逆运算。

然而，我很难理解如何应用这种技术。

假设我在weierstrass曲线上有4个仿射坐标点。仿射加法公式要求两点之间的X坐标差的反式.这意味着我不能把所有的4个点加在一起，只有一个反转。

我可以用一个反转来做P1+P2和P3+P4，但是我需要将P1,2和P3,4相加，这意味着需要另一个反演。因此，如果与乘法相比，反代价较高的话，它的速度要比使用投影坐标慢。

我理解如何将“蒙古语技巧”应用于一次计算一串独立的标量乘法的情况，然后仅用一个逆将所有产生的点转化为仿射系统。但我不明白如何在一个由许多加法组成的乘法中使用它，如果可能的话。

Answer 1

你的分析很有道理。只有当我们有一个相对较多的同时加入点的计算时，才能证明批量反演的成本是合理的。在我从事的一个项目中，我们根据我们的基准设置了70个新增的阈值。如果您感兴趣，我们的代码是这里。

为了稍微概括一下您的示例，可以通过同时添加点对将涉及n点的单个求和简化为包含\lceil n/2 \rceil点的一个求和。因此，我们需要一个相当大的求和(在我们的例子中是140个术语)，或者几个同时求和，来证明倒排的成本是合理的。即便如此，我们最终还是会回到投影公式上，在这种缩减之后，问题的大小会缩小到我们的临界值以下。

在实际应用中，对于单个乘法问题，反演的代价不太可能是合理的，至少假定了256位标量。然而，仿射公式在多标量设置中非常有用。我们使用姚方法的一个多标量变体，它涉及到计算1 \dots 2^w - 1中每个数字的预先计算点的总和。这些求和不仅可能很大，而且相互独立，因此算法的整个第一个(也是最昂贵的)阶段可以看作是2^w - 1同步求和。