实现模运算的更好方法(算法问题)

Question

最近我一直在尝试实现一个模幂运算。我正在用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}
}

So...is这是一个很好的算法，或者至少是一个很好的起点？维基百科并没有真正讨论实现模运算的算法，每当我尝试在其他地方搜索时，我都会发现非常有趣但非常复杂(而且通常是无关的)研究论文和出版物。如果有一个明显的方法来实现这一点，我没有看到，我真的希望得到一些反馈。

Answer 1

老实说，我不知道你在想什么。您谈到了模运算，但通常模运算是在两个数字a和b之间进行的，其结果是a除以b的余数。您的伪代码中的a和b在哪里？

无论如何，也许这会有帮助：a mod b = a - floor(a / b) * b。

我不知道这是不是更快，这取决于你是否可以做除法和乘法，比做很多减法更快。

另一种加快减法速度的方法是使用二进制搜索。如果你想要a mod b，你需要从a中减去b，直到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 + ...

我想二分查找就是你要找的。

Answer 2

对于n位，有许多方法可以在O(log )时间内完成；您可以使用乘法，而不必一次迭代1位。例如,

a mod b = a - floor((a * r)/2^n) * b

哪里

r = 2^n / b

是预先计算的，因为通常情况下您会多次使用相同的b。如果不是，则使用标准的超收敛多项式迭代方法求倒数(在定点迭代2x - bx^2 )。

根据您需要的结果范围选择n (对于许多算法，如模幂运算，它不必是0..b)。

(几十年前，我认为我看到了一个避免连续两次乘法的诀窍……更新:我认为它是Montgomery Multiplication (参见REDC算法)。我收回它，REDC做了与上面更简单的算法相同的工作。不知道为什么会发明REDC。可能由于在链式乘法中使用低阶结果而不是高阶结果而导致延迟稍低？)

当然，如果你有大量的内存，你可以为n = log2(b)..log2(a)预先计算所有的2^n mod b部分和。许多软件实现都是这样做的。

Answer 3

至于模本身，我不确定。作为更大的模幂运算的一部分，你有没有像modular exponentiation上的维基百科页面上提到的那样查找Montgomery multiplication？我研究这种类型的算法已经有一段时间了，但据我回忆，它通常用于快速模幂运算。

edit:乍一看，你的模算法似乎还不错。你基本上是在做除法，这是一个重复的减法算法。