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

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}
}

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

Answer 1

老实说,我不确定你在那里计算什么.请您谈一下模操作,但通常模操作是两个数字之间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 + ...

我认为二进制搜索是你正在寻找的.

Answer 2

有很多方法可以在 O(log n ) 时间内完成n位；你可以用乘法来做，而且你不必一次迭代 1 位。例如，

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

在哪里

r = 2^n / b

是预先计算的，因为通常您会b多次使用相同的值。如果不是，请使用标准的超收敛多项式迭代方法进行倒数（2x - bx^2定点迭代）。

n根据您需要结果的范围进行选择（对于模幂等许多算法，它不一定是0..b）。

（几十年前，我以为我看到了一个避免连续 2 次乘法的技巧......更新：我认为它是蒙哥马利乘法（参见 REDC 算法）。我收回它，REDC 的工作与上面更简单的算法相同。不是确定为什么发明了 REDC ......由于在链式乘法中使用低阶结果而不是高阶结果，可能会稍微降低延迟？）

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

Answer 3

如果你使用shift-and-add进行乘法(这绝不是最快的方法),你可以在每个加法步骤后进行模运算.如果总和大于模数,则减去模数.如果可以预测溢出,则可以同时进行加法和减法.在每一步执行模数也会减小乘数的整体大小(与输入相同而不是双倍).

你正在做的模数的转移正在使你走向全分割算法(模数只是取余数).

编辑这是我在python中的实现:

def mod_mul(a,b,m):
    result = 0
    a = a % m
    b = b % m
    while (b>0):
        if (b&1)!=0:
            result += a
            if result >= m: result -= m
        a = a << 1
        if a>=m: a-= m
        b = b>>1
    return result

这只是模乘(结果= a*b mod m).不需要顶部的模运算,但提醒一下算法假设a和b小于m.

当然,对于模幂运算,你将有一个外部循环,在每个步骤执行整个运算,进行平方或乘法.但我想你知道的.

Answer 4

对于模本身，我不确定。对于作为较大模指数运算一部分的模，您是否查找了有关模幂的维基百科页面中提到的蒙哥马利乘法？我已经有一段时间没有研究这种类型的算法了，但据我记得，它通常用于快速模幂运算。

编辑：就其价值而言，您的模算法乍一看似乎还不错。您基本上是在进行除法，这是一种重复的减法算法。