Scalar-multiplication算法集

1. 引言

ECC金字塔： 该金字塔层级之间不是独立的。 scalar multiplication针对的为：

• （finite, abelian）group G G G，为加法群，计算 k ⋅ P k\cdot P k⋅P，其中 k ∈ Z , P ∈ G k\in \mathbb{Z},P\in G k∈Z,P∈G。
• 而对于乘法群 G ′ G' G′，等价为计算 x k x^k xk，其中 x ∈ G ′ x\in G' x∈G′。

加法群的scalar multiplication 与 乘法群的幂运算，二者算法等价。

Scalar-multiplication广泛用于多种密码学场景中：

• 基于ECDLP的密钥生成
• EC Diffie-Hellman密钥交换
• Schnorr签名

这些场景中都需要计算 k P kP kP。 进一步观察可发现：

• 密钥生成时，点 P P P在编译时是固定的。
• Diffie-Hellman密钥交换时，联合密钥计算时的点是在运行时收到的。
• Schnorr签名验签时，需要double-scalar multiplication k 1 P 1 + k 2 P 2 k_1P_1+k_2P_2 k1​P1​+k2​P2​。Schnorr签名验签时的scalar值 k 1 , k 2 k_1,k_2 k1​,k2​是public的。

以上场景中，存在secret scalar和public scalar的差异：

• 无论 k k k是secret scalar还是public scalar值，计算 k P kP kP的结果应完全相同。

不过在scalar multiplication中需考虑Timing信息问题：

• 某些快速scalar-multiplication算法其运行时长与 k k k值相关。
• 攻击者可测量时长来推断 k k k的信息。
• 如Brumley, Tuveri, 2011：数分钟即可窃取网络中TLS服务的私钥。

因此，当 k k k为secret scalar时，相应的scalar multiplication算法应为constant-time的。

1.1 基于ECDLP的密钥生成

所谓ECDLP（基于椭圆曲线的DLP）为： 已知椭圆曲线上2个点 P 和 Q P和Q P和Q， Q ∈ < P > Q\in

Q∈，找到某整数 k k k，使得 k P = Q kP=Q kP=Q成立。

密码学系统的经典设定为：

• P P P为某固定的系统参数
• k k k为私钥
• Q Q Q为公钥

已知 k 和 P k和P k和P，密钥生成实际是计算 Q = k P Q=kP Q=kP。

1.2 EC Diffie-Hellman密钥交换

EC Diffie-Hellman密钥交换针对的场景为：

• 用户Alice和Bob分别具有密钥对 ( k A , Q A ) 和 ( k B , Q B ) (k_A,Q_A)和(k_B,Q_B) (kA​,QA​)和(kB​,QB​)。
• Alice将其公钥 Q A Q_A QA​发送给Bob
• Bob将其公钥 Q B Q_B QB​发送给Alice
• Alice计算联合密钥 K = k A Q B K=k_AQ_B K=kA​QB​
• Bob计算联合密钥 K = k B Q A K=k_BQ_A K=kB​QA​

1.3 Schnorr签名

Schnorr签名的场景为：

• Alice的密钥对为 ( k A , Q A ) (k_A, Q_A) (kA​,QA​)
• 基点 < P >

  的order为 l l l

• 采用的密码学哈希函数为 H H H

Schnorr签名过程为：

• Alice（签名者）生成密码随机值 r ∈ { 1 , ⋯   , l } r\in\{1,\cdots,l\} r∈{1,⋯,l}，对于消息 m m m进行如下计算获得签名 ( R , s ) (R,s) (R,s)：
  • 计算 R = r P R=rP R=rP
  • 计算 s = ( r − H ( R , m , Q A ) k A ) m o d    l s=(r-H(R,m,Q_A)k_A)\mod l s=(r−H(R,m,QA​)kA​)modl

任何具有Alice公钥 Q A Q_A QA​的人，都可对消息 m m m的签名 ( R , s ) (R,s) (R,s)进行验签，验签过程为：

• 验证 R = s P + H ( R , m , Q A ) Q A R=sP+H(R,m,Q_A)Q_A R=sP+H(R,m,QA​)QA​成立，即验签通过。

2. Scalar-multiplication算法演变

以计算 105 ⋅ P 105\cdot P 105⋅P为例：

• 直观的算法是，直接做104次加法运算： P + P + P + ⋯ + P P+P+P+\cdots +P P+P+P+⋯+P

但是， 105 105 105约有7个bits，需要约 2 7 2^7 27次加法运算。实际真实的scalar值约有 256 256 256个bits，若采用这种直观算法，需要约 2 256 2^{256} 2256次加法运算（比解决ECDLP还昂贵）。

为此，我们需要scalar-multiplication算法的运行时长为与scalar size呈polynomial time关系的。

将 105 105 105表示为： 105 = 64 + 32 + 8 + 1 = 2 6 + 2 5 + 2 3 + 2 0 105=64+32+8+1=2^6+2^5+2^3+2^0 105=64+32+8+1=26+25+23+20

进一步表示为： 105 = 1 ⋅ 2 6 + 1 ⋅ 2 5 + 0 ⋅ 2 4 + 1 ⋅ 2 3 + 0 ⋅ 2 2 + 0 ⋅ 2 1 + 1 ⋅ 2 0 105=1\cdot 2^6+1\cdot 2^5+0\cdot 2^4+1\cdot 2^3+0\cdot 2^2+0\cdot 2^1+1\cdot 2^0 105=1⋅26+1⋅25+0⋅24+1⋅23+0⋅22+0⋅21+1⋅20

根据Horner’s rule有： 105 = ( ( ( ( ( ( ( ( ( ( 1 ⋅ 2 + 1 ) ⋅ 2 ) + 0 ) ⋅ 2 ) + 1 ) ⋅ 2 ) + 0 ) ⋅ 2 ) + 0 ) ⋅ 2 ) + 1 105= ((((((((((1 \cdot 2 + 1) \cdot 2) + 0) \cdot 2) + 1) \cdot 2) + 0) \cdot 2) + 0) \cdot 2) + 1 105=((((((((((1⋅2+1)⋅2)+0)⋅2)+1)⋅2)+0)⋅2)+0)⋅2)+1

从而有： 105 ⋅ P = ( ( ( ( ( ( ( ( ( ( P ⋅ 2 + P ) ⋅ 2 ) + 0 ) ⋅ 2 ) + P ) ⋅ 2 ) + 0 ) ⋅ 2 ) + 0 ) ⋅ 2 ) + P 105\cdot P= ((((((((((P \cdot 2 + P) \cdot 2) + 0) \cdot 2) + P) \cdot 2) + 0) \cdot 2) + 0) \cdot 2) + P 105⋅P=((((((((((P⋅2+P)⋅2)+0)⋅2)+P)⋅2)+0)⋅2)+0)⋅2)+P

相应的计算开销减为：

• 仅需要 6 6 6次double运算 和 3 3 3 次加法运算

扩展为通用“double-and-add”算法表示为：

2.1 single-scalar multiplication double-and-add算法分析

single-scalar multiplication针对的场景是：

• 计算 k P kP kP

将scalar k k k值以二进制表示，其总bits数为 n n n，位为 1 1 1的总个数为 m m m。 double-and-add算法需要：

• n − 1 n-1 n−1次double运算
• m − 1 m-1 m−1次加法运算（平均约为 n / 2 n/2 n/2次加法运算）

double-and-add算法中，无需提前知道 P P P，也没有基于 P P P做预计算。

double-and-add算法：

• 适于处理single-scalar multiplication。
• 运行时间依赖于具体scalar值，对于secret scalar场景下的scalar-multiplication是不安全的。

2.2 double-scalar multiplication double-and-add算法分析

double-scalar multiplication针对的场景是：【也可参看 书本 《Handbook of Elliptic and Hyperelliptic Curve Cryptography 》multi-exponentiation章节的 Algorithm 9.23算法。】

• 计算 k 1 P 1 + k 2 P 2 k_1P_1+k_2P_2 k1​P1​+k2​P2​

直观的算法是：

• 1）计算 k 1 P 1 k_1P_1 k1​P1​（需 n 1 − 1 n_1-1 n1​−1次double运算和 m 1 − 1 m_1-1 m1​−1次加法运算）
• 2）计算 k 2 P 2 k_2P_2 k2​P2​（需 n 2 − 1 n_2-1 n2​−1次double运算和 m 2 − 1 m_2-1 m2​−1次加法运算）
• 3）将以上结果相加（需 1 1 1次加法运算）

以上算法可改进为：（其中 O \mathcal{O} O表示无穷远点） 改进后的算法，计算 k 1 P 1 + k 2 P 2 k_1P_1+k_2P_2 k1​P1​+k2​P2​的开销减为：

• 仅需 m a x ( n 1 , n 2 ) max(n_1,n_2) max(n1​,n2​)次double运算 和 m 1 + m 2 m_1+m_2 m1​+m2​次加法运算。

2.3 为scalar-multiplication引入预计算

对2.2节的算法观察可发现，当 k 1 , k 2 k_1,k_2 k1​,k2​在同一位置具有bit 1 1 1时，总是先加 P 1 P_1 P1​然后再加 P 2 P_2 P2​（出现该情况的概率为 1 / 4 1/4 1/4）。 因此，可先预计算 T = P 1 + P 2 T=P_1+P_2 T=P1​+P2​。

对2.2节的算法进一步改进为：【为Straus algorithm的特例情况】 若预计算是free的（如fixed basepoint, offline precomputation）等场景下，可以：

• 预计算出来一个table，其中包含： 0 P , P , 2 P , 3 P , ⋯ 0P,P,2P,3P,\cdots 0P,P,2P,3P,⋯，当收到 k k k时，仅需查表获得 k P kP kP。

但是，当 k k k很大时，如 k k k为256 bit时，需要的table size为： 3369993333393829974333376885877453834204643052817571560137951281152TB

不过，如果预计算的table中只包含： P , 2 P , 4 P , 8 P , ⋯   , 2 n − 1 P P,2P,4P,8P,\cdots,2^{n-1}P P,2P,4P,8P,⋯,2n−1P。当 n = 256 n=256 n=256时，存储该table的size仅需约 8 K B 8KB 8KB。 对于 k P kP kP这样的single-scalar fixed-basepoint scalar multiplication，相应算法可改进为： 从而可移除fixed-basepoint scalar multiplication中的所有double运算。

2.4 secret scalar 场景下的scalar-multiplication

大多数密码学应用场景下，scalar均为secret的，这就意味着以上算法中的conditional addition中的condition是secret的，为此，可不管condition是啥均做加法运算，相应算法改为： 或者改为，若条件为非1，则与中立元素（无穷远点） O \mathcal{O} O相加： 但是，目前为止，仍未实现secret scalar场景下要求的constant-time属性。

引入table T = ( O , P ) T=(\mathcal{O}, P) T=(O,P)，对以上算法进行重写，此时：

• T [ 0 ] = O ， T [ 1 ] = P T[0]=\mathcal{O}，T[1]=P T[0]=O，T[1]=P
• 相应的scalar multiplication k P kP kP 算法为：

2.5 不以二进制方式来表示scalar值

以上均是以二进制来表示scalar k k k值。 如果以radix 3来表示 k k k，则预计算table T = ( O , P , 2 P ) T=(\mathcal{O},P,2P) T=(O,P,2P)，并将 k k k表示为 ( k n − 1 , ⋯   , k 0 ) 3 (k_{n-1},\cdots,k_0)_3 (kn−1​,⋯,k0​)3​，则 k P kP kP的scalar multiplication算法为： 以更高的radix来表示scalar k k k值：

• 优势是：以更高的radix表示的scalar更短，具有更少的加法运算。
• 劣势是：radix 3 3 3并不足够好，需要做3倍运算。

怎样的radix来表示更优呢？ 4 , 8 , 16 4,8,16 4,8,16？

2.5.1 Fixed-window scalar multiplication

固定窗口宽度为 w w w，预计算table T = ( O , P , 2 P , ⋯   , ( 2 w − 1 ) P ) T=(\mathcal{O},P,2P,\cdots,(2^w-1)P) T=(O,P,2P,⋯,(2w−1)P)，将scalar k k k值以radix 2 w 2^w 2w表示为 ( k m − 1 , ⋯   , k 0 ) 2 w (k_{m-1},\cdots,k_0)_{2^w} (km−1​,⋯,k0​)2w​，整个算法实现是与将二进制scalar切碎进固定长度为 w w w的“窗口”一样，详细的scalar multiplication算法为： 不过，以上算法：

• 对于具有 n n n-bit scalar值，仍然需要 n − 1 n-1 n−1次double运算。
• 预计算table T T T的开销为： w / 2 − 1 w/2-1 w/2−1次加法运算 和 w / 2 − 1 w/2-1 w/2−1次double运算。
• 在for循环中的加法运算次数为： ⌈ n / w ⌉ \left \lceil n/w\right \rceil ⌈n/w⌉。
• 更大的 w w w，意味着更多的预计算。
• 更小的 w w w，意味着for循环中更多的加法运算。
• 对于约 256 256 256-bit的scalar值，通常取 w = 4 或 w = 5 w=4或w=5 w=4或w=5。

2.5.2 Fixed-window scalar multiplication算法是否为constant time?

2.5.1节的Fixed-window scalar multiplication算法是否为constant time?

• 对于该scalar的每个window，需要 w w w次double运算，和 1 1 1次加法运算，似乎可认为是constant time的？

不过，魔鬼在于细节：

• 1）加法运算是否以constant time运行的？即使是与 O \mathcal{O} O的加法运算也是constant time的么？【可让这些加法运算是constant time的，但是具体的实现容易程度以及效率取决于曲线形状（提示：你会想要使用Edward 曲线）。】
• 2）从预计算table T T T中查找是否是以constant time运行的？【通常不是constant time的。】

2.5.3 Cache-timing攻击

Cache-timing攻击针对的场景为： 从tabel T T T中加载位置 p = ( k ) 2 w [ i ] p=(k)_{2^w}[i] p=(k)2w​[i]，该位置为secret scalar的一部分，也应是secret的。 但是，大多是处理器是通过多个缓存来加载数据（这些缓存是透明的，fast memory的）：

• 若该数据在cache中找到了，则加载快速（cache hit）
• 若该数据未在cache中找到，则加载缓慢（cache miss）

为解决该问题，可加载所有items，然后选择正确的那个： 不过，以上算法存在的问题是：

• 1）if-statements不是constant time的。
• 2）comparison无法保证是constant time的。

为此：

• 1）实现constant-time ifs，通用的表达应遵循： 但是所需时间依赖于bit s s s，即使 A , B A,B A,B用时相同。原因在于：branch prediction（分支预测）。 更合适的表达应为： 可将乘法运算和加法运算替换为bit-logic运算（AND和XOR）。对于很快的 A 和 B A和B A和B，其会比if else这种条件分支要快。

• 2）实现constant-time comparison：

2.6 针对fixed-basepoint scalar-multiplication的更多离线预计算

2.3节预计算 P , 2 P , 4 P , 8 P , ⋯ P,2P,4P,8P,\cdots P,2P,4P,8P,⋯之外，结合2.5.1节的fixed-window scalar multiplication，针对 i = 0 , w , 2 w , 3 w , ⋯   , ⌈ n / w ⌉ − 1 i=0,w,2w,3w,\cdots,\left \lceil n/w\right \rceil-1 i=0,w,2w,3w,⋯,⌈n/w⌉−1，预计算相应的 T i = ( O , P , 2 P , 3 P , ⋯   , ( 2 w − 1 ) P ) ⋅ 2 i T_i=(\mathcal{O}, P, 2P, 3P,\cdots,(2^w-1)P)\cdot 2^i Ti​=(O,P,2P,3P,⋯,(2w−1)P)⋅2i。 整个scalar multiplication算法为： 相应的开销为：

• 无需double运算，仅有 ⌈ n / w ⌉ − 1 \left \lceil n/w\right \rceil-1 ⌈n/w⌉−1次加法运算。

可使用更大 w w w，但是：

• 对于某个大 w w w，会使得预计算table无法再载入cache中。
• 对于大 w w w，意味着constant-time load速度将变慢。

2.7 Sliding-window scalar multiplication

2.5.1节的fixed-window scalar multiplication算法为： 运用2.5.1节的fixed-window scalar multiplication算法计算 k P kP kP， k = 22 = ( 1   01   10 ) 2 k=22=(1\ 01\ 10)_2 k=22=(1 01 10)2​，且window size为2时，相应的流程为：

• 初始化 R R R为 P P P。
• double, double, add P P P
• double, double, add 2 P 2P 2P

但是该场景下，效率更高的算法流程应为：

• 初始化 R R R为 P P P。
• double, double, double, add 3 P 3P 3P
• double

这就是fixed-window算法的缺陷：它是固定的。

一个解决思路是：“Slide” the window over the scalar。

Sliding-window scalar multiplication算法思路为：

• 选择window size为 w w w
• 将scalar k k k值重写为 k = ( k 0 , ⋯   , k m ) k=(k_0,\cdots,k_m) k=(k0​,⋯,km​)，其中每个 k i ∈ { 0 , 1 , 3 , 5 , ⋯   , 2 w − 1 } k_i\in\{0,1,3,5,\cdots, 2^w-1\} ki​∈{0,1,3,5,⋯,2w−1}，使得每个长度为 w w w的窗口内最多只有一个非零entry。
• 从右到左扫描 k k k，每遇到 1 1 1-bit 就expand window。
• 预计算 P , 3 P , 5 P , ⋯   , ( 2 w − 1 ) P P,3P,5P,\cdots,(2^w-1)P P,3P,5P,⋯,(2w−1)P。

Sliding-window scalar multiplication具体算法为： 相应的开销为：

• 对于 n n n-bit scalar，仍然需要 n − 1 n-1 n−1次double运算
• 预计算量为 2 w − 1 2^{w-1} 2w−1
• 主循环中加法运算次数的期望值为： n / ( w + 1 ) n/(w+1) n/(w+1)
• 对于相同的 w w w，相比于fixed-window scalar multiplication，其仅需要一半的预计算。
• 对于相同的 w w w，主循环中的加法运算次数更少。

但是sliding-window算法存在的一个问题是：不是以constant time运行的。但仍然适用于验签环境中的double-scalar场景。

3. 使用 efficient negation加速

以上算法适于任意cyclic group < P >

。 但对于椭圆曲线来说，其可提供更多效率优化策略。 例如，基于Weierstrass curves，efficient negation表示为： − ( x , y ) = ( x , − y ) -(x,y)=(x,-y) −(x,y)=(x,−y)

因此，可用有符号（signed）来表示scalar值。

借助efficient negation，可对Fixed-window scalar multiplication进一步做如下优化：

• 将scalar表示为 ( k 0 , ⋯   , k m − 1 ) (k_0,\cdots,k_{m-1}) (k0​,⋯,km−1​)，其中 k i ∈ [ − 2 w , ⋯   , 2 w − 1 ] k_i\in[-2^w,\cdots,2^w-1] ki​∈[−2w,⋯,2w−1]
• 预计算 T = ( − 2 w P , ( − 2 w + 1 ) P , ⋯   , O , P , ⋯   , ( 2 w − 1 ) P ) T=(-2^wP,(-2^w+1)P,\cdots,\mathcal{O}, P,\cdots, (2^w-1)P) T=(−2wP,(−2w+1)P,⋯,O,P,⋯,(2w−1)P)
• 运行正常的fixed-window scalar multiplication。
• 一半的预计算几乎是free的，可get one bit of w w w for free。
• 由于negation很快，可do it on fly（从而节约一半的预计算table，实现更快的constant-time lookups）。

同理，也可借助scalar-negation对sliding-window scalar multiplication进行类似的加速。

4. 使用 efficient endomorphisms加速

Ben展示了在椭圆曲线上存在efficient endomorphisms，以 φ \varphi φ来表示。 假设对于所有的 Q ∈ < P > Q\in

Q∈， φ ( Q ) \varphi(Q) φ(Q)对应 λ Q \lambda Q λQ。

见 (Gallant, Lambert, Vanstone, 2000; and Galbraith, Lin, Scott, 2009)，可借助efficient endomorphisms，可实现更快的scalar multiplication：

• 将scalar k k k表示为 k = k 1 + k 2 λ k=k_1+k_2\lambda k=k1​+k2​λ，其中 k 1 , k 2 k_1,k_2 k1​,k2​长度为 k k k的一半。
• 运行half-size double-scalar multiplication k 1 P + k 2 ⋅ φ ( P ) k_1P+k_2\cdot \varphi(P) k1​P+k2​⋅φ(P)。
• 可节约一半的double运算（预计速度提升约30%~40%）。

借助2个efficient endomorphisms，可实现4-dimensional decomposition。 执行quarter-size quad-scalar multiplication，可再节约25%的double运算。

5. 使用 Differential addition加速（Montgomery ladder优势）

对于形如 B y 2 = x 3 + A x 2 + x By^2=x^3+Ax^2+x By2=x3+Ax2+x的椭圆曲线，Montgomery在1987年展示了如何进行基于 x x x坐标的计算：【为此，以projective坐标系 ( X : Z ) (X:Z) (X:Z)来表示，其中 x = ( X / Z ) x=(X/Z) x=(X/Z)。Montgomery "ladder step"算法。】

• 已知点 P P P的 x x x坐标 x P x_P xP​，点 Q Q Q的 x x x坐标 x Q x_Q xQ​，点 P − Q P-Q P−Q的 x x x坐标 x P − Q x_{P-Q} xP−Q​
• 计算点 R = P + Q R=P+Q R=P+Q的 x x x坐标 x R x_R xR​。

这种计算称为differential addition。 对于其它形状的椭圆曲线，其differential addition效率要低一些。

仅知点 P P P的 x x x坐标，可借助differential addition来高效计算 k P kP kP的 x x x坐标： 使用Montgomery ladder算法的优势在于：

• 非常整齐的结构，易于保护不受timing攻击。
  • 将其中的if statement替换为conditional swap。
  • 仔细处理constant-time swaps。
• 速度很快（不与 具有efficient endomorphisms的曲线相比的话）。
• point压缩和解压缩是free的。
• 易于实现。
• 没有恶心的特例情况（见Bernstein的“Curve25519”论文）。

6. multi-scalar multiplication

multi-scalar multiplication针对的场景为： 计算 Q = ∑ 1 n k i P i Q=\sum_{1}^n k_iP_i Q=∑1n​ki​Pi​

在2.2节看到了 n = 2 n=2 n=2的情况，当 n = 128 n=128 n=128呢？

思路为：假设 k 1 > k 2 > ⋯ > k n k_1>k_2>\cdots >k_n k1​>k2​>⋯>kn​。

Bos-Coster算法为递归计算： Q = ( k 1 − k 2 ) P 1 + k 2 ( P 1 + P 2 ) + k 3 P 3 ⋯ + k n P n Q=(k_1-k_2)P_1+k_2(P_1+P_2)+k_3P_3\cdots +k_nP_n Q=(k1​−k2​)P1​+k2​(P1​+P2​)+k3​P3​⋯+kn​Pn​

在递归计算过程中：

• 每一步都需要一次scalar subtraction运算和一次point addition运算。
• 每一步都“消除” expected log ⁡ n \log n logn scalar bits

Bos-Coster算法：

• 速度可以很快（但不是constant-time的）。
• 需要能快速访问最大的2个scalar值：将scalars放入heap中。
• 实现fast heap对于实现好的性能至关重要。

6.1 fast heap

heap为二叉树，每个父节点都大于其2个子节点。 数据结构以数组的形式存储，在该数组中的位置决定了其在树中的位置。 Root在位置0，左叶子节点在位置1，右叶子节点在位置2。 对于在位置 i i i的节点，其子节点在位置 2 ⋅ i + 1 2\cdot i+1 2⋅i+1和 2 ⋅ i + 2 2\cdot i+2 2⋅i+2，其父节点在位置 ⌊ ( i − 1 ) / 2 ⌋ \left \lfloor (i-1)/2 \right \rfloor ⌊(i−1)/2⌋。

Typical heap root replacement (pop operation)为：从root开始，swap down for a variable amount of times。

Floyd‘s heap为：swap down to the bottom, swap up for a variable amount of times。

Floyd‘s heap的优势为：

• 每个swap-down step仅需要一次比较（而不是2次）
• swap-down loop对branch predicators更友好。

7. finite-field inversion

根据Fermat定理可知， x p − 1 ≡ 1 m o d    p x^{p-1}\equiv 1\mod p xp−1≡1modp，从而可知求倒数对应为幂运算： x − 1 ≡ x p − 2 m o d    p x^{-1}\equiv x^{p-2} \mod p x−1≡xp−2modp。

不过这种幂运算实际与scalar multiplication并无本质差异（double运算变为了square运算，加法运算变为了multiplication运算）。

由于素数 p p p是公开的，因此 p − 2 p-2 p−2也是公开的。

思路一：采用sliding window来进行幂运算。

但是 p p p不仅是公开的，而且是固定的系统参数，有更好的方案么？ 答案是：addition chains

所谓addition chains，定义为： 令 k k k为正整数，若序列 s 1 , s 2 , ⋯   , s m s_1,s_2,\cdots,s_m s1​,s2​,⋯,sm​满足如下条件，则可称其为 k k k的长度为 m m m的addition chain：

• s 1 = 1 s_1=1 s1​=1
• s m = k s_m=k sm​=k
• 对于每个 s i s_i si​，存在 j , k < i j,k