我最近一直试图实现模块化指数器.我正在用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}
}
所以...这是一个很好的算法,或者至少是一个好的开始？维基百科并没有真正讨论用于实现模运算的算法,每当我尝试在其他地方搜索时,我发现它真的很有趣,但却非常复杂(通常是无关的)研究论文和出版物.如果有一种明显的方法可以实现这一点,我没有看到,我真的很感激一些反馈.