0

我希望这里的一些大师可以帮助我

我正在编写一个 C/C++ 代码来使用 SHA1 作为散列算法来实现一致性散列。

我需要实现模块操作如下:

0100 0011....0110 100 mod 0010 1001 = ?

如果除数 ( 0000 1111) 是 2 的幂pow(2,n),那么很容易,因为最后 n 位被除数就是结果。

SHA1 长度为 160 位(或 40 hexa)。我的问题是如何实现一个长位串到另一个任意位串的模运算?

谢谢你。

4

1 回答 1

1

正如用户斯塔克在评论中指出的那样(我认为比必要的更粗鲁),这只是以 2^32 为基数的长除法。或以 2 为底,有更多位数。你可以使用你在学校学到的以 10 为底的长除法算法。

有更好的算法可以对更大的数字进行除法,但是对于您的应用程序,我怀疑您可以按照以下几行非常简单且低效地进行操作(这是base-2版本,仅相当于从左侧减去-改变分母的版本,直到你不能再这样做):

// Treat x,y as 160-bit numbers, where [0] is least significant and
// [4] is most significant. Compute x mod y, and put the result in out.
void mod160(unsigned int out[5], const unsigned int x[5], const unsigned y[5]) {
  unsigned int temp[5];
  copy160(out, x);
  copy160(temp, y);
  int n=0;
  // Find first 1-bit in quotient.
  while (lessthanhalf160(temp, x)) { lshift160(temp); ++n; }
  while (n>=0) {
    if (!less160(out, temp)) sub160(out, temp); // quotient bit is 1
    rshift160(temp); --n; // proceed to next bit of quotient
  }
}

为免生疑问,以上只是一个粗略的草图:

  • 它可能充满了错误。
  • 我还没有编写构建块函数的实现,例如less160.
  • 实际上,您可能只是将那些内联代码而不是单独的函数。例如,copy160只是五个作业,或一个短循环,或一个memcpy.

它肯定可以提高效率。例如,第一步可能会更好地计算前导 0 位,然后进行一次移位,而不是一次移位一个位置。(不过,右移可能不想这样做,因为有一半的时间你只做一次移位。)

“base-2^32”版本可能会更快,但实现会稍微复杂一些。

于 2016-04-13T11:59:07.940 回答