コンシステントハッシュ法のSHA1剰余演算

Question

私はここにいくつかの第一人者が、私はハッシュアルゴリズムとしてSHA1を使用して一貫性のあるハッシュを実装するためのC/C++のコードを書いています

私を助けることができる願っています。

Iは以下のようにモジュールの動作を実装する必要があります。配当の最後のNビットが結果であるように、それが容易になり、

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

除数（0000 1111）は2 pow(2,n)の累乗である場合。

SHA1の長さは160ビット（または40ヘキサ）です。私の質問は、私はどのように他の任意のビット列に長いビット文字列のモジュロ演算を実装するのですか？

ありがとうございます。

Answer 1

ユーザーとして、スタークは、コメントで、（これは思っていたよりもはるかに珍しく、私は思う）と指摘しています。または基数2で、より多くの数字で。そして、あなたは、基数10のために学校で学んだ長時間の除算アルゴリズムを使うことができます。

非常に大きな数字で除算を行うためのより良いアルゴリズムがありますが、あなたは非常に単純で非効率的、次の行（これはあなたが、もはやそうすることはできないまでちょうど分母の左シフトバージョンをオフ差し引いになるベース-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は、わずか5つの割り当て、または短いループ、またはmemcpyです。

確かに効率的にすることができます。一度に1つの場所をシフトするのではなく、先行する0ビットをカウントしてから1つのシフトを行う方がよい場合があります。 （右シフトはおそらくそれをやりたいとは思わないかもしれませんが、半分の時間シフトを行うためです）

"base-2^32"の方が速いかもしれませんが、実装は少し複雑になります。