[發明專利]模乘運算的實現方法和裝置

有效

• 申請號: 201110041611.7
• 申請日: 2011-02-21
• 公開（公告）號: CN102646033A
• 公開（公告）日: 2012-08-22
• 發明（設計）人: 潘無窮;荊繼武;劉宗斌
• 申請（專利權）人: 中國科學院研究生院
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 謝安昆;宋志強

1.一種模乘運算的實現方法，其特征在于，包括：

A、接收輸入的乘數x、y，模數n；其中，x和y的位數均為k，n的位數為j，j≤k，x、y和n均為正整數；

令n’＝n＜＜t，y’＝y＜＜t，t為正整數，＜＜表示左移；

B、計算s＝(x×y’)mod?n’，mod表示求模運算，包括：

B1、令s＝0，i＝k+t-1；

B2、計算s＜＜1+x×y’[i]，得到計算結果s’，y’[i]表示y’的第i位的取值；

B3、計算s’mod?n’，得到計算結果s”；

B4、令s＝s”，如果i等于0，則執行步驟C；否則，令i＝i-1，并返回執行步驟B2；

C、令s”’＝s＞＞t，將s”’作為模乘運算的結果輸出。

2.根據權利要求1所述的方法，其特征在于，所述步驟B3包括：

B31、令a為s’的高h位，b為n’的高h位，h為正整數；

B32、將a和b進行比較，如果a＞b，則計算s”＝s’-n’，并令s’＝s”，然后返回執行步驟B31，否則，輸出s”。

3.根據權利要求2所述的方法，其特征在于，所述步驟B3采用二級流水線結構實現；其中，第一級流水線進行a和b的比較以及s”的高h位的計算，第二級流水線進行s”的除高h位以外的其它位的計算。

4.根據權利要求3所述的方法，其特征在于，所述第一級流水線采用非冗余結構的普通加法實現，所述第二級流水線采用冗余結構的加法實現。

5.根據權利要求2、3或4所述的方法，其特征在于，

如果j＝k，則t的取值需要滿足以下條件：大于log₂k、大于h，且小于k；

如果j＜k，則t的取值需要滿足以下條件：大于log₂k+(k-j)、大于h+(k-j)，且小于k。

6.一種模乘運算的實現方法，其特征在于，包括：

A、接收輸入的乘數x、y，模數n；其中，x、y和n的位數均為k，且x、y和n均為正整數；

令n’＝n＜＜t，y’＝y＜＜t，t為正整數，＜＜表示左移，并且，k和t均需要能夠被正整數k₁整除；

B、計算s＝(x×y’)mod?n’，mod表示求模運算，包括：

B1、令s＝0，i＝k/k₁+t/k₁-1；

B2、計算s＜＜k₁+x×y’[(i+1)×k₁-1∶i?×k₁]，得到計算結果s’，y’[(i+1)×k₁-1∶i×k₁]表示y’的第(i+1)×k₁-1位到第i×k₁位中的每位的取值；

B3、計算s’mod?n’，得到計算結果s”；

B4、令s＝s”，如果i等于0，則執行步驟C；否則，令i＝i-1，并返回執行步驟B2；

C、令s”’＝s＞＞t，將s”’作為模乘運算的結果輸出。

7.一種模乘運算的實現裝置，其特征在于，包括：

第一處理單元，用于接收輸入的乘數x、y，模數n，其中，x和y的位數均為k，n的位數為j，j≤k，x、y和n均為正整數；令n’＝n＜＜t，y’＝y＜＜t，t為正整數，＜＜表示左移；令s＝0，i＝k+t-1；

第二處理單元，用于計算s＜＜1+x×y’[i]，得到計算結果s’，y’[i]表示y’的第i位的取值；計算s’mod?n’，得到計算結果s”，mod表示求模運算；令s＝s”，如果i等于0，則令s”’＝s＞＞t，將s”’作為模乘運算的結果輸出，否則，令i＝i-1，并重復執行自身功能。

8.一種模乘運算的實現裝置，其特征在于，包括：

第一處理單元，用于接收輸入的乘數x、y，模數n，其中，x、y和n的位數均為k，且x、y和n均為正整數；令n’＝n＜＜t，y’＝y＜＜t，t為正整數，＜＜表示左移，并且，k和t均需要能夠被正整數k₁整除；令s＝0，i＝k/k₁+t/k₁-1；

第二處理單元，用于計算s＜＜k₁+x×y’[(i+1)×k₁-1∶i×k₁]，得到計算結果s’，y’[(i+1)×k₁-1∶i×k₁]表示y’的第(i+1)×k₁-1位到第i×k₁位中的每位的取值；計算s’mod?n’，得到計算結果s”，mod表示求模運算；令s＝s”，如果i等于0，則令s”’＝s＞＞t，將s”’作為模乘運算的結果輸出；否則，令i＝i-1，并重復執行自身功能。