[發明專利]提高大整數Montgomery模乘運算速度的方法

無效

• 申請號: 200710304567.8
• 申請日: 2007-12-28
• 公開（公告）號: CN101470598A
• 公開（公告）日: 2009-07-01
• 發明（設計）人: 程登峰;張慶勝;王磊;丁瑤
• 申請（專利權）人: 航天信息股份有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72;H04L9/14
• 代理公司: 北京科龍寰宇知識產權代理有限責任公司
• 代理人: 孫皓晨;朱世定

1、一種提高大整數Montgomery模乘運算速度的方法，其特征在于，其包括的步驟為：

步驟a：將兩個大整數乘數X、Y分別拆分為高數位和低數位

步驟b：并行計算X_haY_hb，X_laY_lbr^-n?modM；

步驟c：計算的值，得到最終結果；

其中M為大整數，r＝2^w為最小字處理單元，n為大整數M的字個數。

2、根據權利要求1所述的提高大整數Montgomery模乘運算速度的方法，其特征在于，所述步驟b中計算mod?M的步驟為：

步驟b11：取i＝0；

步驟b12：令C＝0，從j＝0到依次計算(C，S)＝T[j]+X_ha[j]*Y_lb[i]+C；T[j]＝S；從到j＝n-1依次計算(C，S)＝T[j]+C；T[j]＝S；

步驟b13：令(C，S)＝T[n]+C；T[n]＝S；T[n+1]＝C；C＝0；m＝T[0]*M′[0]mod?r；

步驟b14：令(C，S)＝T[0]+m*M′[0]，從j＝1到n-1依次計算(C，S)＝T[j]+m*M[j]+C；T[j-1]＝S；

步驟b15：令(C，S)＝T[n]+C；T[n-1]＝S；T[n]＝T[n+1]+C；

步驟b16：如果返回T[0]...T[n-1]；否則令i＝i+1，執行上述步驟b12；

其中，i、j、C為變量，M為大整數，r＝2^w為最小字處理單元，n為大整數M的字個數，M′[0]＝M^-1[0]mod?r。

3、根據權利要求1所述的提高大整數Montgomery模乘運算速度的方法，其特征在于，所述步驟b中計算的步驟為：

步驟b21：令i＝0；

步驟b22：令C＝0，從j＝0到依次計算(C，S)＝T[j]+X_ha[j]*Y_lb[i]+C；T[j]＝S；從到j＝n-1依次計算(C，S)＝T[j]+C；T[j]＝S；

步驟b23：令(C，S)＝T[n]+C；T[n]＝S；T[n+1]＝C；C＝0；m＝T[0]*M′[0]mod?r；

步驟b24：令(C，S)＝T[0]+m*M′[0]，從j＝1到j＝n-1依次計算(C，S)＝T[j]+m*M[j]+C；T[j-1]＝S；

步驟b25：令(C，S)＝T[n]+C；T[n-1]＝S；T[n]＝T[n+1]+C；

步驟b26：如果返回T[0]...T[n-1]；否則令i＝i+1，執行上述步驟b22；

其中，i、j、C為變量，M為大整數，r＝2w為最小字處理單元，n為大整數M的字個數，M′[0]＝M^-1[0]mod?r。

4、根據權利要求1所述的提高大整數Montgomery模乘運算速度的方法，其特征在于，所述步驟b中計算X_laY_lbr^-nmod?M的步驟為：

步驟b31：令i＝0；

步驟b32：令C＝0，從j＝0到依次計算(C，S)＝T[j]+X_ha[j]*Y_lb[i]+C；T[j]＝S；

從到j＝n-1；依次計算(C，S)＝T[j]+C；T[j]＝S；

步驟b33：令(C，S)＝T[n]+C；T[n]＝S；T[n+1]＝C；C＝0；m＝T[0]*M′[0]mod?r；

步驟b34：令(C，S)＝T[0]+m*M′[0]，從j＝1到j＝n-1依次計算(C，S)＝T[j]+m*M[j]+C；T[j-1]＝S；

步驟b35：(C，S)＝T[n]+C；T[n-1]＝S；T[n]＝T[n+1]+C；

步驟b36：如果則i＝i+1，執行上述步驟b32；

步驟b37：令

步驟b38：令C＝0；m＝T[0]*M′[0]mod?r；

步驟b39：令(C，S)＝T[0]+m*M′[0]，從j＝1到j＝n-1依次計算(C，S)＝T[j]+m*M[j]+C；T[j-1]＝S；

步驟b3A：(C，S)＝T[n]+C；T[n-1]＝S；T[n]＝T[n+1]+C；

步驟b3B：如果i<n-1，則令i＝i+1并執行上述步驟b38；否則返回T[0]...T[n-1]；

其中，i、j、C為變量，M為大整數，r＝2^w為最小字處理單元，n為大整數M的字個數，M′[0]＝M^-1[0]mod?r。