高效模乘方法及装置

摘要

本发明包含一种改进的蒙哥马利方法及其运算电路，本发明模乘方法在现有FIOS基础上作了改进，改变了对字的处理顺序，从而对中间结果K进行存储，减少了访问外部存储的次数；本发明模乘器，包含存储单元、临时结果存储单元、乘法单元和加法单元，其中存储单元为双端口RAM(110)用来存储数据，包括输入乘数X、被乘数Y、初始常数MC、模数M、中间结果K和最后结果Result；临时存储单元为锁存器(101、102、103、104和105)，用来锁存临时结果，其中第一w+1位锁存器(101)和第二w位锁存器(102)用来存储加法单元输出的进位、高w位和低w位，第三w位锁存器(103)用来存储输出到存储单元的最终结果的部分字，第四和第五w位锁存器(104和105)用来对从存储单元的输入进行锁存；加法单元第一和第二w位加法器(106、107)用来对第一w位锁存器(101)和第二w位锁存器(102)锁存的临时结果和乘法单元的输出进行加法运算；第三w位加法器(108)对乘法单元的输出结果相加得到中间结果K；乘法单元w*w位乘法器(109)用来计算w*w位的乘法，输出为C、S结果；各部件执行本发明方法中的运算。本发明不仅降低了芯片面积，而且还减少了模乘运算的时钟周期数。

主权项

1.一种适合硬件实现的多字高基的蒙哥马利模乘方法，其特征在于：乘数X、被乘数Y和模数M均为n位的二进制数，w为算法每次处理的字长，MC为w位的常数，中间变量K为n位的二进制数，中间变量C，S均为w位的二进制数，Carrybit为一位的二进制数，最终结果Result为n位的二进制数，i，j为循环变量，l＝n/w，运算前变量C，S，Carrybit，Result均赋零值，其运算步骤如下：(a)将X的第0个字与Y的第0个字相乘，乘积的低w位赋给S，高w位赋给C；(b)将S与MC相乘后，求其对模2w的余数，结果赋给K的第0个字；(c)将K的第0个字与M的第0个字相乘，乘积结果与C，S相加后，低w位赋给S，高w位赋给C；进位赋给Carrybit；(d)将C的值赋给S，Carrybit赋给C的最低一位，其余位均置0，Carrybit位置0；(e)令j为1开始外循环；(f)令i为1开始内循环；(g)将K的第i-1个字与M的第j+1-i个字相乘，乘积结果与Carrybit，C，S组成的2w+1位的二进制数相加，结果的低w位赋给S，高w位赋给C；进位赋给Carrybit，循环变量i加1，重复内循环直至i等于j，退出内循环；(h)令i为0开始内循环；(i)将X的第i个字与Y的第j-i个字相乘，乘积结果与Carrybit，C，S组成的2w+1位的二进制数相加，结果的低w位赋给S，高w位赋给C；进位赋给Carrybit，循环变量i加1，重复内循环直至i等于j，退出内循环；(j)将S与MC相乘后，求其对模2w的余数，结果赋给K的第j个字；(k)将K的第j个字与M的第0个字相乘，乘积结果与Carrybit，C，S组成的2w+1位的二进制数相加后，低w位赋给S，高w位赋给C；进位赋给Carrybit；(l)将C的值赋给S，Carrybit赋给C的最低一位，其余位均置0，Carrybit位置0；(m)循环变量j加1，重复外循环直至j等于l-1，退出外循环；(n)令j为1-2开始外循环；(o)令i为0开始内循环；(p)将K的第l-1-j+i个字与M的第l-1-i个字相乘，乘积结果与Carrybit，C，S组成的2w+1位的二进制数相加，结果的低w位赋给S，高w位赋给C；进位赋给Carrybit，循环变量i加1，重复内循环直至i等于j，退出内循环；(q)令i为0开始内循环；(r)将X的第l-1-j+i个字与Y的第l-1-i个字相乘，乘积结果与Carrybit，C，S组成的2w+1位的二进制数相加，结果的低w位赋给S，高w位赋给C；进位赋给Carrybit，循环变量i加1，重复内循环直至i等于j，退出内循环；(s)将S的值赋给Result的第l-2-j个字；(t)将C的值赋给S，Carrybit赋给C的最低一位，其余位均置0，Carrybit位置0；(u)循环变量j加1，重复外循环直至j等于0，退出外循环；(v)将S的值赋给Result的第l-1个字