11/04/02 17:30:37.60 Q5oVwEC4P
【12桁トリップ検索速度】
うーむ、やっぱり俺の苦手＆嫌いな確率統計の話しが、がっつり入ってきそうだな…
誰か、そういうの得意な人が厳密にやってくれて算出方法を公開してくれないかなぁ…
考え方自体は高校数学のレベルだと思うんで…
１．まず注意しなければならないのは、例えば5完の場合の組み合わせは
64^5=1073741824通りであるが、SHA1全体の状態空間は64^20=約1000000000000000000000000000000000000通りあるので
1073741824通り検索したからといって、目的の5完が100%出るという保証は無いということ。
２．また、トリップ検索ツールの多くはランダム要素を取り入れてる。
１、２から、SHA1全体の状態空間は12完程度の状態空間に対して十分に大きいので、
サイコロを振ったようなイメージで考える。（←ここがそもそも怪しい）
例えば、1～6の目があるサイコロをn回振ったときに6の目がある確率p(n)は
p(n) = 1 - (5/6)^n となる。
6回振ると、約65%の確率。100%にはほど遠いことに注意。
ってな感じで、300MTrips/sの場合の目安(全単射と仮定した場合で確率75%程度で出る時間の目安)を考えると…
5完： 4.5秒
6完： 5分20秒
7完： 5時間40分
8完： 15日
9完： 963日
10完： 168年
11完： 1万年
12完： 70万年
50%の場合は、多分、だいたい>>126で良いと思う。