[發明專利]一種減少預計算的標量乘算法

在審

• 申請號: 202210229644.2
• 申請日: 2022-03-07
• 公開（公告）號: CN114611051A
• 公開（公告）日: 2022-06-10
• 發明（設計）人: 楊曉秋;田新雨;孫海旭
• 申請（專利權）人: 哈爾濱理工大學
• 主分類號: G06F17/10
• 分類號: G06F17/10
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種減少預計算的標量乘算法，這種算法的特征是：

第一步，輸入標量k和窗口寬度w；

第二步，預計算出f(i)＝f(i-1)+f(i-2),i＞＝2，其中f(0)＝P,f(1)＝2P，并且預計算時最大值不超過(2^w-1)P,例如當窗口寬度w為4時，預計算{1P,2P,3P,5P,8P,13P}；

第三步，利用wNAF算法確定k鏈中的值，判斷k對2取余是否為0，若為0，則e_i＝0，若不為0，則e_i＝k mod 2^w，k＝k-e_i，k＝k/2，此輪運算結束，下一輪繼續判斷k對2取余是否為0，直至得到整個k鏈；

第四步，通過第三步得到的k鏈進行標量乘計算Q＝k*P得到標量乘Q。

2.根據權力特征1所述的一種減少預計算的標量乘算法，其特征在于第一步：w窗口寬度范圍是{2，3，4，5，6，7，8，9，10，11}。通常當w＝4時，在此算法中降低得計算復雜度更加明顯。

3.根據權力特征1所述的一種減少預計算的標量乘算法，其特征在于第二步:對于預計算數列，每個數都是前兩個數之和，只需要點加運算就能完成預計算，當窗口寬度為4時，由第三步得到的k鏈中，非零數值是由{P,3P,5P,...,15P}組成，共存儲8個點，本發明中已經預計算出{1P,2P,3P,5P,8P,13P}，共存儲6個點，減少了預計算的個數。

4.根據權力特征1所述的一種減少預計算的標量乘算法，其特征在于第四步：通過第二步的預計算，會產生差值，但是差值很小為P,只需一次點加運算就能彌補差值，例如k鏈中存在非零數值7P時，7P＝8P-P。

5.根據權力特征1所述的一種減少預計算的標量乘算法,其特征在于第四步：在進行標量乘計算時，進行到點加運算時，執行運算Q＝Q+k_iP，k_i等于|e_i|，k_iP是第二步預計算出來的，由{1P,2P,3P,5P,8P,13P}和P相加減得到，減少了預計算的個數，進而減少了標量乘計算的復雜度。