积模2^N±1的快速算法  

An Efficient Computation for Product Modulo 2 N ±1

作　　者：胡久乡[1] 卢正鼎[1] 

机构地区：[1]华中理工大学计算机科学与技术学院

出　　处：《华中理工大学学报》1999年第3期104-106,共3页Journal of Huazhong University of Science and Technology

摘　　要：提出了一种利用一个运算器计算两个２Ｎ－位整数乘积按２Ｎ＋１和２Ｎ－１取模的算法．这种算法依赖于整数字节间卷积的加法和平方运算，而不依赖于其乘法运算．由于平方运算是一元运算，所以在使用ＲＯＭ查表情况下，可以大大节省ＲＯＭ位数，从而提高算法的效率和通用性．An efficient algorithm is presented for simultaneously computing the products of two 2N bit integers modulo 2 N +1 and modulo 2 N -1 from their k bit byte decompositions. Cyclic convolution can be computed by using only additional and squaring operation, but not two operand operation. Since the squaring operation is one operand operation, significant savings in ROM bits can be obtained if look up tables are used.

关 键 词：卷积 积模 ROM 算法 快速算法 运算器 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]