第⼆⼗六个知识点：描述NAF标量乘法算法
第⼆⼗六个知识点：描述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} \neq 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←∞.
booth算法乘法例题讲解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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。