[發(fā)明專利]基于UCPS協(xié)議的快速模乘方法及硬件實(shí)現(xiàn)方法

無效

• 申請?zhí)枺?/td>: 200810044187.X
• 申請日: 2008-12-25
• 公開（公告）號(hào): CN101763240A
• 公開（公告）日: 2010-06-30
• 發(fā)明（設(shè)計(jì)）人: 閔敬國;袁世強(qiáng)
• 申請（專利權(quán)）人: 上海華虹集成電路有限責(zé)任公司
• 主分類號(hào): G06F7/72
• 分類號(hào): G06F7/72
• 代理公司: 上海浦一知識(shí)產(chǎn)權(quán)代理有限公司 31211
• 代理人: 丁紀(jì)鐵

1.一種基于UCPS協(xié)議的快速模乘方法，其特征在于：它是在現(xiàn)有的移位-加算法的基礎(chǔ)上，將每次移位1比特位，改為將每次移位16比特位，將加法器轉(zhuǎn)化為減法器；

設(shè)，輸入192位x，y??192位模值n；

輸出xy?mod?n；

具體實(shí)現(xiàn)的步驟如下：

步驟1、初始化x`＝y(tǒng)[191:176]×x；

步驟2、令i從12到1循環(huán)，

x`[192:0]＝x`[191:0]+x`[209:192]×(～n)//～n表示n的補(bǔ)碼，

x`＝x`＜＜16，

s＝x`+y[(i×16-1):(i-1)×16]×x；

步驟3、s＝x`[191:0]+x`[209:192]×(～n)；

步驟4、若(s[192]＝1)，則s＝s+(～n)；

步驟5、返回s；

其中：n＝ffffffffffffffffffffffffffffffffffffffffffffefff，x`，x，y，n，s均為192比特位數(shù)，i為0-191的整數(shù)。

2.一種基于UCPS協(xié)議的快速模乘硬件實(shí)現(xiàn)方法，其特征在于：采用兩級(jí)流水線結(jié)構(gòu)；

第一級(jí)流水線為相乘流水線，計(jì)算：y[(i×16-1):(i-1)×16]×x；

第二級(jí)流水線為取模流水線，計(jì)算：x`[191:0]+x`[209:192]×(～n)；

基本運(yùn)算單元為16位乘法器和16位加法器，將192比特位×16比特位運(yùn)算分解為12次16比特位×16比特位運(yùn)算；192比特位+192比特位運(yùn)算分解為12次16比特位+16比特位運(yùn)算，其中：x`，x，y，n均為192比特位數(shù)，i為0-191的整數(shù)。

3.如權(quán)利要求2所述的方法，其特征在于：

第一級(jí)流水線按16比特位分組完成兩個(gè)192比特位相乘計(jì)算，結(jié)果存儲(chǔ)在存儲(chǔ)單元mul_qp中；當(dāng)啟動(dòng)計(jì)算，一個(gè)時(shí)鐘脈沖信號(hào)mm_start有效時(shí)，控制x移位的計(jì)數(shù)器cnt_a和控制y移位的計(jì)數(shù)器cnt_b清0，cnt_a計(jì)數(shù)達(dá)到16時(shí)cnt_b進(jìn)位；如果取輸入乘數(shù)mm_b[191:176]乘輸入乘數(shù)mm_a時(shí)，輸入乘數(shù)mm_a依次移位送輸入乘數(shù)mm_a[15:0]、mm_a[31:16]……到16位乘法器MULT16X16，cnt_a＝11時(shí)乘法器完成16比特位×192比特位的計(jì)算，cnt_a＝15時(shí)相乘結(jié)果完全存儲(chǔ)到存儲(chǔ)單元mul_qp中；

第二級(jí)流水線對存儲(chǔ)單元mul_qp的值取模，左移16bit，取模過程為：result[191:0]＝mul_qp[191:0]+mul_qp[209:192]×(～n)。