可扩展高基蒙哥马利模乘算法及其电路结构

摘要

本发明属集成电路技术领域，具体为一种可扩展高基蒙哥马利模乘算法及其电路结构。本发明是对多字高基蒙哥马利模乘器的改进，其中，每一步对模数N和被乘数B进行左移位操作，对中结果S不作移位操作，使数据通路的流水线级间的延迟从二个时钟周期缩短为一个时钟周期。其电路结构包括用于存放模乘运算3个操作数A、B和N的3个存储器、由第1—第P级处理单元组成的流水线形式的数据通路模块、用于控制整个模乘器运算过程的控制模块和一个先进先出的存储器等。本发明大大提高了模乘运算速度，同时对中间结果的存储单元进行了改进，使其硬件开销减小。

主权项

1、一种可扩展高基蒙哥马利模乘算法，其特征在于以多字高基蒙哥马利模乘算法为基础，每一步对模乘的被乘数B和模数N进行左移位操作，对中间结果S不作移位操作，从而使数据通路的流水线级间的延迟由2个时钟周期减小到一个时钟周期，具体步骤如下：首先模数N(0)、被乘数B(0)以及k+1位的a0进入第一级流水线，经过一个时钟周期运算得到和结果SS(0)和进位SC(0)；第二个时钟周期将N(0)和B(0)左移k位，还有SS(0)和SC(0) 传递到第二级流水线进行运算，同时N(1)、B(1)进入第一级流水线进行运算；这样经过p级PE的流水线运算，中间运算结果从第p级的PE输出；下面分两种情况，如果e＞p，中间结果从第p级PE输出时，第1级PE仍然在运算高位的N(i)和B(i)，所以将输出的中间结果通过CLA加和后存入FIFO，直到N(e-1)和B(e-1)通过第1级PE运算后，再将FIFO中的中间结果依次读入流水线第1级PE开始运算；如果e≤p，则当中间结果从第p级PE输出时，第1级PE已经空闲，所以输出的中间结果SS(0)和SC(0)通过移位处理后直接进入第1级PE进行运算；这里，PE为处理单元，N为模数，B为被乘数，SS为和结果，SC为进位结果，CLA为提前进位加法器，FIFO为先进先出存储器模块；这里，e＝n/w，n为模数N的倍数，w为处理单元的数据宽度。