基于重编码的快速标量乘算法

Fast algorithm of scalar multiplication based on recoding

采用回溯法设计出一种重编码算法。该算法只需对标量序列进行一次变换、至多四个中间变量,以及只需基于比特位比较赋值操作,效率更高,利于硬件实现标量乘法,并证明了所得结果具有正则序列的性质。该算法应用到计算数字签名中常用的gP+hQ时,得到g、h的具有最小联合重量序列。

This paper designed a recoding algorithm which scans the sequence of the scalar only once, employed four intermediate variables at most as well as comparisons and evaluations on digits. The algorithm was more efficient and more convenient to application of scalar multiplication on hardware, The result is proved to possess the character of the canonical representation. When the algorithm is applied to compute gP ＋ hQ in digital signatures, the result is unique, optimal and has the least joint weight.