50 ビットのハッシュしか生成しない SHA1 のバリアントに対して、Haskell で誕生日攻撃プログラムを作成したいと考えています。これを行うには、約を格納できるハッシュテーブルが必要です。2^25 エントリ。
このマップのキーはInt64、値は短い文字列 (~ 16 バイト) になります。
どのハッシュ実装を使用するかについての提案はありますか?
(最後の更新は無視してください。2^50 要素のビット配列が必要です。)
1502 次
2 に答える
6
1 ピースあたり 8 バイトの 2^25 エントリの場合、データだけで 768MB のようなストレージが見られます。おそらくバイト文字列を格納するための実際のオーバーヘッドで約 3 ギガバイトです。バイト文字列あたり 80 バイトを推測すると、ハッシュテーブルが得られます。 /map の内部構造、およびキーのボックス化など。
これは、問題を比較的健全に保つまともなマシンのメモリに常駐するもの全体を保存できることを意味しますが、収集時間はちょっとひどいものになります.
キースペースをパーティション分割することで、より小さなハッシュ テーブルを多数使用することをお勧めします。これにより、使用するハッシュ テーブルに関係なく、多数の更新を並行して実行できます。
実装に関して：
IORefs の unordered-containers からのファンアウトの広いもののような不変のハッシュ テーブルの束をラップし、ある種の atomicModifyIORef や ryan newton の比較およびスワップ プリミティブのようなものを使用するか、古い Data.HashTable 実装を使用してみることができます。簡単な命令的な方法で。
後者は、unordered-containers で使用されるハッシュ配列マップ試行よりも対数係数によって漸近線を改善しますが、Data.HashTable には不適切な定数があります。ただし、問題の規模では、これらの要因はおそらく相殺されます。
于 2012-04-04T01:46:02.613 に答える