PHP / MySQLで一意のコードを生成しますか？

StackOverflow https://stackoverflow.com/questions/219475

質問

私は、雑誌のスクラッチオフカード、ボトルキャップ賞品などで使用される数百万の英数字コードを生成する必要があるクライアントと協力しています。キャップに印刷するのに十分短い必要があり、1とI、0とOなどのあいまいな文字が含まれないようにし、将来の使用のために明示的に保存する必要があります-誰かがそれを引き換えようとするときに「有効性」を決定するアルゴリズムを持っているだけです。最後に、彼らはコードが大きな「コードスペース」内にランダムに分散されることを確認したい。人々がアルファベットを歩いて追加のコードを推測することはできません。

これらの種類のコードセットを生成するための合理的に効率的なアルゴリズムへのポインタはありますか？封筒の裏側にいくつか傷を付けましたが、この問題は不注意な人のtrapのような臭いがします。

役に立ちましたか？

解決

（たとえば）約1000万の一意のキーが必要な場合、最良のアプローチは、指数関数的に大きいキースペースを選択し、ランダムに生成を開始することです。 Birthday Paradox について読んでください。これが主な懸念事項です。 2 ^ n個の一意で安全なキーが必要な場合は、少なくとも2 ^（2 * n）の可能な値があることを確認してください。大まかなO（n log n）アルゴリズムは次のとおりです。

  • 少なくとも2 ^ 50のキースペースを使用する（つまり、2 ^ 50の一意の値を許可する）と、データセット全体で衝突がほとんどなくなります。そのうちの2 ^ 25個を試してみると、鍵を取得する確率がほぼ均等になります。
  • 必要な数の乱数を生成
  • キーでデータベースのインデックスを作成します（これはO（n lg n）ステップ：ソートです）
  • DBをページングし、データセット全体を反復処理して重複を削除します（以下の擬似コード）
  • 重複行を削除すれば完了です。

擬似コード：

$last = null;
while ($current = getnext()) {
    if ($last == $current) {
        push($toDelete, $current);
    }
    $last = $current;
}

他のヒント

たとえば、明確な上、下、数字の40個の記号の文字セットを使用できると仮定します。

n個の文字のシーケンスの場合、40個の n の組み合わせがあります

  • 40 4 = 2,560,000
  • 40 5 = 102,400,000
  • 40 6 = 4,096,000,000
  • 40 7 = 163,840,000,000
  • 40 8 = 6,553,600,000,000

このように8文字を使用すると作業に十分なスペースが得られます。1,000万個のコードを生成した場合、コードをブルートフォースするには数十万の組み合わせを試す必要があります。

または、別の方向からアクセスします-可能なコードの数、を呼び出すトラップを避けるために生成する コードの数を指定します"http://en.wikipedia.org/wiki/Birthday_paradox" rel = "nofollow noreferrer">誕生日のパラドックス？

8文字のコードを取得すると、6,553,600,000,000は約2 42 なので、そこから2 21 コード、または2,097,152

を合理的に生成できます。

ワンタイムパスワードアルゴリズムを使用しますか

RFC4225は、HMACアルゴリズムに基づいたものを詳しく説明しています。

http://www.ietf.org/rfc/rfc4226.txt

ただし、0〜9桁のbase10エンコードを使用する代わりに、base32を使用します。

どの方法を使用する場合でも、1桁目または2桁目を＆quot; first-line＆quot;として追加することをお勧めします。誤って入力したり、番号を発明しようとする人々に対する防御。

奇妙なことに、次のシードでは32個の一意の文字列しか生成できませんでした。

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

より長いシードを使用して、より多くの-生成された40,000個の一意の文字列を正常に生成できました。

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top