奎斯扩特减少

摘要

一种用于计算第一数字X和第二数字Y的积P再模N的方法以及设备，其中Y被分割为长度均为p比特的j个字，并且X具有(m+n)比特的长度，对Y的连续的j个字进行循环操作，执行所形成的中间积的中间模数的减少。使用特别选择的N的倍数的N’，以便只有基于N’的中间积的单个减少来确保中间积P在每个周期结束时从未长于(m+n)比特。N’是N的整数倍，并选择值N’，以使得(m－1)个最高有效比特等于‘1’，而最低有效比特是‘0’。

主权项

1.一种用于计算第一个数字X和第二个数字Y的积P再模N的方法，其中Y被分割为长度均为p比特的j个字，并且X具有(m+n)比特的长度，所述方法包括以下步骤：a)初始化(21)乘积寄存器P；b)将Y的j个字的第一个载入乘法器；c)将所载入的Y的字乘以(23)X以形成中间积T；d)利用T和P*2p的和来更新(24)乘积寄存器P；e)通过减去值PH(N’/2)来减少(25)乘积寄存器P的内容；f)将Y的j个字的相继一个载入乘法器，并且为Y的j个字的每个重复步骤c)至e)，其中N’是N的整数倍，而选择值N’以便使得(m-1)个最高有效比特等于‘1’，并且最低有效比特是‘0’，以及其中将PH选为寄存器中P的(p+2)个最高有效比特。