最近我一直在尝试实现模块化指数运算器。我正在用VHDL编写代码，但正在寻找更多算法性质的建议。模块化指数运算器的主要组件是模块化乘法器，我也必须自己实现。我的乘法算法没有任何问题-它只是加法和移位，而且我很好地弄清楚了所有变量的含义，以便我可以在相当长的时间内进行乘法。
我遇到的问题是在乘法器中实现模运算。我知道执行重复的减法会起作用，但是它也会很慢。我发现可以移动模数以有效地减去模数的大倍数，但我认为可能还有更好的方法。我正在使用的算法的工作原理如下（奇怪的伪代码）：
result,modulus : integer (n bits) (previously defined)
shiftcount : integer (initialized to zero)
while( (modulus<result) and (modulus(n-1) != 1) ){
modulus = modulus << 1
shiftcount++
}
for(i=shiftcount;i>=0;i--){
if(modulus<result){result = result-modulus}
if(i!=0){modulus = modulus >> 1}
}
所以...这是一个好的算法，还是至少是一个好的起点？ Wikipedia并未真正讨论实现模运算的算法，每当我尝试在其他地方搜索时，我都会发现非常有趣但非常复杂（且通常不相关）的研究论文和出版物。如果有一种我看不到的明显方法可以实现，我将非常感谢您的反馈。
我不确定您在说什么，说实话。您谈论的是模运算，但是通常模运算在两个数字a和b之间，其结果是a除以b的余数。您的伪代码中的a和b在哪里？]
无论如何，也许会有所帮助：a mod b = a - floor(a / b) * b。
我不知道这是否更快，这取决于您是否可以比许多减法更快地进行除法和乘法。
加快减法方法的另一种方法是使用二进制搜索。如果需要a mod b，则需要从b中减去a，直到a小于b。因此，基本上，您需要找到k这样：
a - k*b < b, k is min
找到此k的一种方法是线性搜索：
k = 0;
while ( a - k*b >= b )
++k;
return a - k*b;
但是您也可以对它进行二进制搜索（只运行了一些测试，但是对所有这些都有效）：
k = 0;
left = 0, right = a
while ( left < right )
{
m = (left + right) / 2;
if ( a - m*b >= b )
left = m + 1;
else
right = m;
}
return a - left*b;
我想二进制搜索解决方案在处理大数时将是最快的。
如果要计算a mod b并且只有a是大数（可以将b存储在原始数据类型上，则可以更快地执行此操作：
for each digit p of a do
mod = (mod * 10 + p) % b
return mod
这有效，因为我们可以将a写为a_n*10^n + a_(n-1)*10^(n-1) + ... + a_1*10^0 = (((a_n * 10 + a_(n-1)) * 10 + a_(n-2)) * 10 + ...
我认为您正在寻找二进制搜索。
如果您对乘法使用移位加法（这绝不是最快的方法），则可以在每个加法步骤之后进行模运算。如果总和大于模数，则减去模数。如果可以预测溢出，则可以同时进行加法和减法。在每一步进行模运算也会减小乘法器的整体大小（与输入相同，而不是两倍）。
您正在执行的模数转换使您大部分方式都转向了全除法算法（模只剩下余数）。
EDIT这是我在python中的实现：
def mod_mul（a，b，m）：结果= 0a = a％mb = b％m而（b> 0）：如果（b＆1）！= 0：结果+ = a如果结果> = m：结果-= ma = a＆lt <1如果a> = m：a- = mb = b >> 1返回结果
这只是模块化乘法（结果= a * b mod m）。不需要顶部的模运算，但是提醒我们该算法假定a和b小于m。
当然，对于模幂运算，您将有一个外循环，该外循环在进行平方或乘法的每一步都完成整个操作。但是我想你知道。
对于模本身，我不确定。对于更大的模块化指数运算的一部分进行模运算，您是否按Montgomery multiplication的维基百科页面中所述查找modular exponentiation？自从我研究这种算法以来已经有一段时间了，但是据我所记得，它通常用于快速模块化指数运算。
edit：的价值，您的模算法乍一看似乎还可以。您基本上是在做除法，这是一种重复的减法算法。
那个测试(modulus(n-1) != 1) //有点测试？
-似乎与(modulus<result)组合在一起。
针对硬件实现的设计，我会意识到比测试隐含的逻辑（相减）要多于按位运算并分支到零的测试，它更小/更大。
如果我们可以轻松进行按位测试，则可能很快：
m=msb_of(modulus)
while( result>0 )
{
r=msb_of(result) //countdown from prev msb onto result
shift=r-m //countdown from r onto modulus or
//unroll the small subtraction
takeoff=(modulus<<(shift)) //or integrate this into count of shift
result=result-takeoff; //necessary subtraction
if(shift!=0 && result<0)
{ result=result+(takeoff>>1); }
} //endwhile
if(result==0) { return result }
else { return result+takeoff }
（未经测试的代码可能包含陷阱）
[result重复递减modulus，移位以匹配最高有效位。
[每次减法后：result大约有50/50的机会丢失1 msb以上。它也有〜50/50变负的机会，减去一半的加法将总是再次使其变为正数。 >如果shift不为0，则应放回正数]
[欠载result并且'shift'为0时，工作循环退出。
有很多方法可以在O（log n