第二十六个知识点：描述NAF标量乘法算法

NAF标量乘法算法是标量乘法算法的一种增强，该算法使用了非邻接形式（Non-Adjacent Form)表达，减少了算法的期望运行时间。下面是具体细节：

让(k)是一个正整数，(P)是一个在域(F_q)上椭圆曲线(E)上的点。这个计算乘法操作(Ｑ = k * P)就是圆曲线上的标量乘法操作（点乘）。一个最简单计算的方法就是基于双倍-加法的霍纳规则的变体。顾名思义，该方法最突出的两个构建块是点加倍和点添加原语。就像名字那样，算法也十分简单。把(k)写成

[k=k_{n-1}2^{n-1}+k_{n-2}2^{n-2}+ cdots +k_{1}+k_{0} ]

，其中(k in {0,1},i = 0,1,2,...,n-1)。下面有两种算法来表达。

INPUT: k = (kt−1,..., k1, k0)2, P ∈ E(Fq).

OUTPUT: k ⋅ P.

Q←∞.

For i from 0 to t−1 do

If ki = 1 then Q←Q+P.

P←2P.

Return(Q).

INPUT: k = (kt−1,..., k1, k0)2, P ∈ E(Fq).

OUTPUT: k ⋅ P.

Q←∞.

For i from t−1 down to 0 do

Q←2Q.

If ki = 1 then Q←Q+P.

Return(Q).

第一个算法计算(k)从右到左，第二个算法计算从左到右。在一个二进制表示中，1的数量大概是t/2=m/2。因此期望的运行时间是

[frac{m}{2} * A + m * D ]

。

在1951年，Booth[3]提出了一个新的标量二进制表达被叫做有符号二进制方法。然后Rietweisner[4]证明了每个整数在这种表达下都是独一无二的[5]。尤其，如果(p=(x,y) in E(F_q))，那么有(-P=(x,x+y))，如果(F_q)是二进制域。同时如果(F_q) 的阶大于3，就有(-P = (x,-y))。计算减法就会很有效。这让我们想出了另一种有符号整数的表达方式。(k = sum^{l-1}_{i=0}k_i * 2^i)，其中(k_i in {0,+,-})。一个十分有用的有符号整数表达就是不相邻范式(NAF)。NAF的形式就是上面那样，但是规定了 (k_{l-1} eq 0)，同时没有两个相邻的(k_i)都是0。NAF的长度是(l)。

NAF的性质[1]

每个正整数k都有独一无二的NAF表达。记作NAF(k)。
NAF(k)有所有(k)的有符号表达最少的非零数字。
NAF(k)的长度最多比二进制表达多一个。
如果NAF(k)的长度是l,那么有(frac{2^l}{3}<k<frac{2^{l+1}}{3})。
在所有长度为(l)的NAF中，非零系数的概率约为1/3。

NAF(k)能够通过下面的算法有效率的计算。

INPUT: A positive integer k.
OUTPUT: NAF(k).
i←0.
While k≥1 do
If k is odd then: ki ←2−(k mod 4), k←k−ki;
Else: ki ←0.
k←k/2, i←i+1.
Return(ki−1, ki−2,..., k1, k0).

最后一个算法给出了我们可以用NAF(k)代替k[1]的二进制表示来修改标量乘法从左到右的二进制方法：

INPUT: Positive integer k, P ∈ E(Fq).
OUTPUT: k ⋅ P.
Based on previous algorithm compute NAF(k) =∑l−1i=0ki⋅2i.
Q←∞.
For i from l−1 down to 0 do
Q←2Q.
If ki = 1 then Q←Q+P.
If ki = −1 thenQ←Q−P.
Return(Q).

基于NAF的第三个和第四个属性，我们能计算上述算法的平均时间复杂度。

[frac{m}{3} * A + m * D ]

[1] Hankerson, Darrel, Scott Vanstone, and Alfred J. Menezes. "Guide to elliptic curve cryptography". Springer Science & Business Media, 2004.
[2] Jonathan Taverne, Armando Faz-Hernández, Diego F. Aranha, Francisco Rodríguez-Henríquez, Darrel Hankerson, Julio López. "Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction", Journal of Cryptographic Engineering, Vol. 1, No 3, pp. 187-199, 2011.
[3] A.D.Booth, “A Signed binary multiplication technique”, Journal of Applied Mathematics, Vol. 4. No. 2, pp.236-240, 1951
[4] G.W.Reitwiesner, “Binary Arithmetic”, Advances in computers, Academic Press, Vol. 1, pp.231-308, 1960
[5] Karthikeyan, E. “Survey of elliptic curve scalar multiplication algorithms.” International Journal of Advanced Networking and Applications, Vol. 4, No 2, pp. 1581-1590, 2012