[發明專利]優化的蒙哥馬利模乘硬件

有效

• 申請號: 201410037782.6
• 申請日: 2014-01-26
• 公開（公告）號: CN103761068B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 劉紅明;周玉潔;朱念好
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 上海新天專利代理有限公司31213
• 代理人: 張澤純

1.一種優化的蒙哥馬利模乘方法，其特征在于，乘數A、乘數B和模數N都是n位的二進制數，w為每次處理的字長，s為模數N的字長個數，n0為w位的常數，中間變量m、中間變量S均為w位的二進制數，中間變量C為（w+1）位的二進制數，最終結果T為n位的二進制數，i、j為循環變量，運算前，標量C、S、T均賦值0，該方法包括以下步驟：

步驟1、令i為0開始外循環；

步驟2、將A的第0個字與B的第0個字相乘，乘積結果再與T的第0個字相加，將相加結果的低w位賦給S，高（w+1）位賦給C；

步驟3、將S與n0相乘后，取低w位賦給m；

步驟4、將m與N的第0個字相乘，乘積結果與（C,S）組成的（2w+1）位二進制數相加后，低w位賦給S，高（w+1）位賦給C；

步驟5、令j為1開始內循環；

步驟6、將m與N的第j個字相乘，乘積結果與C的第j個字相加后，再與T的第j個字相加，相加結果的低w位賦給S，高（w+1）位賦給C；

步驟7、將A的第j個字與B的第j個字相乘，乘積結果與（C,S）組成的（2w+1）位二進制數相加，相加結果的低w位賦給S，高（w+1）位賦給C，并將S賦給T的第（j-1）個字，循環變量j加1，重復內循環直至j等于（s-1），退出內循環；

步驟8、將T的第s個字與C進行相加，相加結果的低w位賦給S，高（w+1）位賦給C；

步驟9、將s賦給T的第（s-1）個字，將C的低w位賦給T的第s個字，循環變量i加1，重復內循環直至i等于（s-1），退出外循環；

步驟10、如果T>N，則將T減N之后再賦值給T。

2.一種優化的蒙哥馬利模平方方法，其特征在于，乘數A、乘數B和模數N都是n位的二進制數，w為每次處理的字長，s為模數N的字長個數，n0為w位的常數，中間變量m、中間變量S為w位的二進制數，中間變量C為（w+1）位的二進制數，最終結果T為n位的二進制數，i、j為循環變量，運算前，標量C、S、T均賦值0，該方法包括如下步驟：

步驟1、令i為0開始外循環；

步驟2、將A的第0個字與B的第0個字相乘，乘積結果再與T的第0個字相加，將相加結果的低w位賦給S，高（w+1）位賦給C；

步驟3、將S與n0相乘后，取低w位賦給m；

步驟4、將m與N的第0個字相乘，乘積結果與（C，S）組成的（2w+1）位二進制數相加后，低w位賦給S，高（w+1）位賦給C；

步驟5、令j為1開始內循環；

步驟6、將m與N的第j個字相乘，乘積結果與C的第j個字相加，再與T的第j個字相加，相加結果的低w位賦給S，高（w+1）位賦給C；

步驟7、如果i等于0或者i等于j，則將A的第j個字與B的第j個字相乘，乘積結果與（C,S）組成的（2w+1）位二進制數相加，相加結果的低w位賦給S，高（w+1）位賦給C；

如果i小于j，則將A的第j個字與B的第j個字相乘，乘積結果的2倍再與（C,S）組成的（2w+1）位二進制數相加，相加結果的低w位賦給S，高（w+1）位賦給C，接下來將S賦給T的第（j-1）個字；

循環變量j加1，重復內循環直至j等于（s-1），退出內循環；

步驟8、將T的第s個字與C進行相加，相加結果的低w位賦給S，高（w+1）位賦給C；

步驟9、將s賦給T的第（s-1）個字，將C的低w位賦給T的第s個字，循環變量i加1，重復內循環直至i等于（s-1），退出外循環；

步驟10、如果T>N，則將T減N之后再賦值給T。