15

我最近一直在尝试实现一个模块化指数器。我正在用 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}
}

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

4

5 回答 5

13

老实说，我不确定你在计算什么。您谈论模运算，但通常模运算是在两个数字a和之间b，其结果是除以的余a数b。a你的伪代码中的and在哪里b......？

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

我不知道这是否更快，这取决于您是否可以比很多减法更快地进行除法和乘法运算。

另一种加速减法的方法是使用二分搜索。如果你愿意，a mod b你需要减去直到小于b。所以基本上你需要找到这样的：aabk

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 + ...

我认为二进制搜索是您正在寻找的。

于 2010-05-05T14:13:37.400 回答
6

如果您使用移位加法进行乘法运算（这绝不是最快的方法），您可以在每个加法步骤之后进行模运算。如果总和大于模数，则减去模数。如果你能预测溢出，你可以同时做加法和减法。在每一步进行模运算也将减少乘法器的整体大小（与输入长度相同而不是两倍）。

您正在做的模数的移动使您大部分时间都朝着全除法算法前进（模只是取余数）。

编辑这是我在 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

这只是模乘法（result = a*b mod m）。顶部的模运算不是必需的，但可以提醒算法假设a并且b小于m.

当然，对于模幂运算，您将有一个外部循环，它在每一步执行整个操作，执行平方或乘法。但我想你知道这一点。

于 2010-05-05T14:56:11.440 回答
6

There are many ways to do it in O(log n) time for n bits; you can do it with multiplication and you don't have to iterate 1 bit at a time. For example,

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

where

r = 2^n / b

is precomputed because typically you're using the same b many times. If not, use the standard superconverging polynomial iteration method for reciprocal (iterate 2x - bx^2 in fixed point).

Choose n according to the range you need the result (for many algorithms like modulo exponentiation it doesn't have to be 0..b).

(Many decades ago I thought I saw a trick to avoid 2 multiplications in a row... Update: I think it's Montgomery Multiplication (see REDC algorithm). I take it back, REDC does the same work as the simpler algorithm above. Not sure why REDC was ever invented... Maybe slightly lower latency due to using the low-order result into the chained multiplication, instead of the higher-order result?)

Of course if you have a lot of memory, you can just precompute all the 2^n mod b partial sums for n = log2(b)..log2(a). Many software implementations do this.

于 2019-10-20T06:04:26.210 回答
0

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

编辑：对于它的价值，你的模算法乍一看似乎还可以。你基本上是在做除法，这是一个重复的减法算法。

于 2010-05-05T13:56:48.207 回答
0

那个测试(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 时退出。

于 2010-05-08T20:27:08.383 回答