これは基本的に数学の問題ですが、非常にプログラミングに関連しています。URL を含む 10 億の文字列があり、それぞれの MD5 ハッシュの最初の 64 ビットを取得すると、どのような衝突頻度が予想されるでしょうか?

URL が 1 億しかない場合、答えはどのように変わりますか?

衝突は非常にまれであるように私には思えますが、これらは混乱を招く傾向があります。

MD5 以外のものを使用した方が良いでしょうか? 注意してください、私はセキュリティを探しているのではなく、高速なハッシュ関数を探しているだけです。また、MySQL のネイティブ サポートも優れています。

編集：まったく重複していません

デモンストレーションのために、ハッシュ化されたときに衝突する文字列の例をいくつか挙げてください。MD5 は比較的標準的なハッシュ オプションであるため、これで十分です。

10 個の int のリストには、10 個あります。可能な順序または順列。5000回試行しただけでrandom.shuffleが重複するのはなぜですか?

編集: FWIW、1 つのペアに対して 2 つの同じものがない確率が次の場合: p = (10! - 1) / 10! 組み合わせの数は: C = 5000! / 4998! ※2！= 5000 * 4999 / 2 重複する確率は次のとおりです。

randint のランダム性をテストするためにこれを行いました。

約 10 倍以上試してみたところ、最高の結果はリピーターの前に 121 回の繰り返しでした。これは、標準ライブラリから得られる最良の結果ですか?

私は Random クラスでいくつかのテストを行っており、次のコードを使用しました。

rnd の最大制限 (つまり 5000000) を変更し続け、反復回数を変更したところ、次の結果が得られました。

なぜこれらの平均値を取得しているのか、つまり、各値を 10 回チェックしたうち、80% の確率でこの平均範囲内に収まっています。ランダムに近いとは言えないと思います。

かなり乱数を取得するにはどうすればよいですか。

ウィキペディアで説明されている誕生日効果の解釈を手伝ってください。

誕生日攻撃は次のように機能します。

1. 任意のメッセージ m を選択し、h(m) を計算します。
2. リスト L を更新します。h(m) がリスト L にあるかどうかを確認します。
3. (h(m),m) が既に L にある場合、衝突するメッセージのペアが見つかりました。それ以外の場合は、ペア (h(m),m) をリスト L に保存し、ステップ 1 に戻ります。

誕生日のパラドックスから、約 2^(n/2) 回のハッシュ評価を実行した後、一致するエントリを見つけることが期待できることがわかります。

上記は、上記のループ全体を 2^(n/2) 回繰り返すことを意味しますか (つまり、2^(n/2) はステップ 1 に戻ります)、またはすでに L にある個々のアイテムとの 2^(n/2) 比較を意味しますか? ?

インターネット上には、有名な誕生日のパラドックスについて論じている膨大なリソースがあります。2 人の誕生日が同じである確率を計算する方法は明らかですP(same) = 1 - P(different)。しかし、明らかにもっと単純なことを自問自答すると、失速してしまいます。まず、2 つのランダムな誕生日を生成するとします。同じ誕生日を迎えることは、コインを投げるようなものです。2 人の誕生日が同じ (Heads) か、誕生日が同じでない (Tail) かのいずれかです。これを 500 回実行すると、最終結果 (#Heads/500) は何とか 0.5 に近くなります。

• Q1) しかし、3 つのランダムな誕生日を生成した場合、これについてどのように考えればよいでしょうか? ではどうすれば確率を見積もることができるでしょうか？明らかに、私のコインの類推は当てはまりません。

• Q2) 上記を理解したら、スケールアップして 30 または 50 の誕生日を生成する必要があります。大きなセットから同一の誕生日を分離するための推奨される手法またはアルゴリズムはありますか? それらを配列に入れてループする必要がありますか?

これが私が必要だと思うものです：

Q1)

Q2)

• 2 つの複製用の配列、3 つの複製用の配列、および 3 つ以上の複製用の配列を作成します。
• 生成された各誕生日を 1 つずつ最初の配列に追加します。ただし、そうする前に、配列をループして、既にそこにあるかどうかを確認してください。その場合、それを 2 番目の配列に追加しますが、その前に上記のプロセスを繰り返します。
• しかし、それは非常に効率的なアルゴリズムではないようです :) ここで Big O を改善するための提案はありますか?

Pythonで誕生日のパラドックスを解決しようとしています。私は近くにいますが、最後の部分は私を途方に暮れさせます。ランダムを使用して、作成するアイテムの範囲と数を指定して番号のリストを生成しています。それはうまくいきます。

次に、リスト（上記で生成）に重複がないかどうかを確認します。それはうまくいきます。

次に、指定された（n）個のリストを生成しようとします。ここで私は問題にぶつかります。1つのリストを生成し、「NoneType」を返します。反復可能ではありません。私が困惑しているのは、リストは生成されますが、Pythonはそれをリストとして認識していません。

コードは次のとおりです。

結果は次のとおりです。

次のものが与えられたとします。

• ハッシュの長さ
• 衝突の可能性

さて、上記を知った上で、与えられた確率パーセンテージを取得するために必要な「サンプル」の数をどのように取得できますか?

次の問題が発生します。

何かご意見は？私はpython 2.7を実行しています