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

程石 等: 基于两种新标量表示的安全高效标量乘算法 4553

3.3 wJRF 标量形式
注意到 JRF 算法只是调整了 k 和 的表示方式, 从而使得在 JRF 的相同位置上都满足一个为 0, 另一个为 ±1.
l
此基础上, 将窗口方法的思想应用到 JRF 形式上, 使得算法中出现的非 0 值不局限于 ±1, 定义 wJRF 如下: 设
w
l
l
k
(k n−1 ,...,k 0 ) 和 (l n−1 ,...,l 0 ) 分别为 和 的有符号二进制表示, 窗口宽度为 , 如果 k 和 满足 k mod 2 w−1 ≡ 0 且
(
(
)
l mod 2 w−1 / ≡ 0 . 且对于任意 i ∈ [1,n−2] k i 和 l i 满足 (k i ,l i ) = 0,±2 w−2 ) 或 (k i ,l i ) = ±2 w−2 ,0 , 此时将 (k n−1 ,...,k 0 ) 和
,
(l n−1 ,...,l 0 ) 称为窗口联合正则形式 (wJRF). 关于多标量的 wJRF 有如下重要性质.
定理 2. wJRF 存在且唯一.
证明: 首先证明 wJRF 的存在性, 最直接的方法是给出一个计算 wJRF 结构的算法.
对于一对整数 (k,l) 满足 k mod 2 w−1 ≡ 0 且 l mod 2 w−1 / ≡ 0, 在 JRF 算法的基础上给出类似的 wJRF 算法: 首先,
由于整数 (k,l) 满足 k mod 2 w−1 ≡ 0 且 l mod 2 w−1 / ≡ 0, 显然 k 0 和 l 0 一个为 0 而另一个非 0, 假设非 0 值为 λ, 满足
0 ⩽ |λ| ⩽ 2 w−2 . 这是由于给出的 wJRF 只要求 k mod 2 w−1 ≡ 0 并且 l mod 2 w−1 / ≡ 0, 对于 wJRF 形式的其他位置的非
0 值, 显然只有 ±2 w−1 , 因此接下来, 首先来观察 (k 1 ,l 1 ) 的情况.
(1) 假设 (k 1 ,l 1 ) = (0,0), 为了保证在调整表示后的结果与原先一致, 令 e λ = λ−2 w−1 mod 2 w−1 , 此时只会出现下面
两种情况之一:

k 1 k 0 k 1 k 0 k 1 k 0 k 1 k 0
0 λ 2 w−1 e λ 0 0 0 0
⇒ , ⇒
0 0 0 0 0 λ 2 w−1 e λ
l 1 l 0 l 1 l 0 l 1 l 0 l 1 l 0
w
t
此时显然 2·2 w−1 +λ−2 = λ, 前后表示结果一致, 此时计算过程中的 s 和 无需调整;
(
(2) (k 1 ,l 1 ) = 2 w−1 ,2 w−1 ) , 令 e λ = λ−2 w−1 mod 2 w−1 , 同样地, 为了满足 w-JRF 格式, 必然会导致下面两种情况
之一:

k 1 k 0 k 1 k 0 k 1 k 0 k 1 k 0
2 w−1 λ 0 e λ 2 w−1 0 2 w−1 0
⇒ , ⇒
2 w−1 0 2 w−1 0 2 w−1 λ 0 e λ
l 1 l 0 l 1 l 0 l 1 l 0 l 1 l 0
(
t
此时 k 和 l 满足了 wJRF 格式的要求, 但是显然 s 和 需要补充变动后缺少的值 2 w−1 , 因此 s ← s−2k 1 +2 w−1 )/ 2,
( )/
t ← t −2l 1 +2 w−1 2.
(3) k 1 和 l 1 一个为 0 而另一个非 0, 满足格式, 正常进行.
(4) 对于任意的 (k i ,l i )(1 < i ⩽ n−1), 由于此时任意位数可能存在的非 0 值均为 ±2 w−1 , 因此上述对 e λ 的处理实
e λ = −λ mod 2 w−1 , 与 JRF 算法计算过程近似, 证毕.
际上等价于
下面证明 wJRF 的唯一性.
假设有两个长度为 n 的不同 wJRF 表示:

 ( )
k = (k n−1 ,...,k 0 ) = k ′ ,...,k ′
 n−1 0
 ( ) (7)
 l = (l n−1 ,...,l 0 ) = l ′ ,...,l ′
n−1 0
其中, ′ l i , l 的最小值并且:
′
i
j 是满足 k i , k 或 i
 ( ) ( )
 s = k n−1 ,...,k j = k ′ ,...,k ′

 n−1 j

 ( ) ( ) (8)
 ′ ′
 t = l n−1 ,...,l j = l ,...,l

n−1 j
′ k 非 ′ w−1 w−1 . 不失一
由于 k 和 l 可交换, 不失一般性, 假设 k i , k . 此时必然有 k j 和 j 0, 其中一个为 2 , 另一个为 −2
i
′
′
般性, 假设 k j = 2 w−1 , k = −2 w−1 . 这样通过 wJRF 的定义可知有 l j = l = 0.
j
j
此时, 假设 s ≡ 2 w−1 mod 2 w+1 , 根据 wJRF 的定义有 k j+1 = 0 且 k ′ j+1 =±2 w−1 , 这样显然可以得出 l j+1 = ±2 w−1 且 l ′ j+1 = 0,
w
t ≡ 2 mod 2 w+1 t ≡ 0 mod 2 w+1 s ≡ 2 +2 w−1 mod 2 w+1 ,
w
这样前者说明 而后者说明 , 该矛盾表明最初的假设错误. 假设
同样可以得到类似的结论. 唯一性得证.