Page 149 - 《软件学报》2025年第10期

4546 软件学报 2025 年第 36 卷第 10 期

3. for i = c−1 down to 0 do
4. Q = [2]Q;
5. if k w [i] , 0 then
6. Q = Q+ P [i]; /*其中 P [i] = [k w [i]]P+R 为预计算的点*/
′
′
′
7. end if
8. end for
9. return Q−R.
1.2 联合正则形式算法
l
k
设 (k n−1 ,...,k 0 ) 和 (l n−1 ,...,l 0 ) 分别为 和 的有符号二进制表示, 满足 k +l ≡ 1(mod2), 并且如果对于任意的 i,
k i 和 l i 均满足 (k i ,l i ) = (0,±1) 或 (k i ,l i ) = (±1,0), 则 (k n−1 ,...,k 0 ) 和 (l n−1 ,...,l 0 ) 称为联合正则形式 (JRF) [17] . JRF 的生成
算法如算法 5.
算法 5. JRF 生成算法 [17] .

输入: 一对整数 (k,l) 满足 k +l ≡ 1(mod2);
:
输出: JRF (k,l) (k n−1 ,...,k 0 ) (l n−1 ,...,l 0 ).
,
,
,
1. i ← 0 s ← k t ← l;
2. while s > 0 or k > 0 do
,
3. k i = s mod 2 l i = t mod 2;
4. if (k i ,l i ) = (0,0) then
,
,
,
5. k i ← k i−1 k i−1 ← −k i−1 l i ← l i−1 l i−1 ← −l i−1 s ← s/2 t ← t/2;
,
,
6. else if (k i ,l i ) = (1,1) then
,
,
,
,
,
7. k i ← 1−k i−1 k i−1 ← −k i−1 l i ← 1−l i−1 l i−1 ← −l i−1 s ← (s−2k i +1)/2 t ← (t −2l i +1)/2;
8. else
,
9. s ← (s−k i )/2 t ← (t −l i )/2;
10. end if
11. i ← i+1;
12. end while
13. n ← i;
14. return (k n−1 ,...,k 0 ) (l n−1 ,...,l 0 ).
,
基于 JRF 生成算法的多标量乘算法如算法 6.
算法 6. JRF 多标量乘算法 [17] .
:
,
,
输入: 椭圆曲线上两点 P,Q JRF (k,l) (k n−1 , ...,k 0 ) (l n−1 , ...,l 0 );
输出: [k]P+[l]Q.
1. R ← O;
2. for i = n−1 down to 0 do
3. R = [2]R;
4. if k i , 0 then
R = R+[k i ]P;
5.