Генерация уникальных кодов в PHP / MySQL?

Question

Я работаю с клиентом, которому необходимо сгенерировать миллионы буквенно-цифровых кодов, используемых в скретч-картах журналов, призах в бутылочных крышках и так далее. Они должны быть достаточно короткими, чтобы их можно было печатать на колпачке, они хотят убедиться, что неоднозначные символы, такие как 1 и I, 0 и O и т. Д., Не включены, и они должны быть явно сохранены для будущего использования - мы можем ' просто есть алгоритм, который определяет «действительность», когда кто-то пытается его выкупить. Наконец, они хотят убедиться, что коды случайно распределены внутри большого «кодового пространства», чтобы люди не могли просто угадать дополнительные коды, проходя по алфавиту.

Есть ли какие-нибудь указатели на достаточно эффективные алгоритмы для генерации таких кодовых наборов? Я поцарапал несколько штук на обратной стороне конверта, но эта проблема пахнет ловушкой для неосторожных.

Answer 1

Если вам нужно около 10 миллионов уникальных ключей (например), лучше всего выбрать пространство ключей, которое экспоненциально больше, и начать генерировать случайным образом. Прочитайте о Парадоксе Дня Рождения - это главное, о чем вам следует беспокоиться. Если вы хотите 2 ^ n уникальных и безопасных ключей, убедитесь, что есть как минимум 2 ^ (2 * n) возможных значений. Вот грубый алгоритм O (n log n):

• Используйте пространство ключей не менее 2 ^ 50 (другими словами, допустите 2 ^ 50 возможных уникальных значений), и у вас практически не будет коллизий во всем наборе данных - и любой, кто перебирает ваши ключи, будет есть шанс получить ключ, если они попробуют 2 ^ 25 из них.
• сгенерируйте столько случайных чисел, сколько вам нужно
• индексировать базу данных по вашему ключу (это шаг O (n lg n): сортировка)
• пролистать БД и перебрать весь набор данных для обрезки дубликатов (псевдокод ниже)
• Удалите повторяющиеся строки, и все готово.

псевдокод:

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

Answer 2

Предположим, вы можете использовать набор символов, скажем, из 40 символов однозначных верхних, нижних и цифровых символов.

Для последовательности из n символов у вас есть 40 ⁿ комбинаций

• 40 ⁴ = 2 560 000
• 40 ⁵ = 102 400 000
• 40 ⁶ = 4 096 000 000
• 40 ⁷ = 163 840 000 000
• 40 ⁸ = 6 553 600 000 000

Таким образом, 8 символов дают довольно хорошее пространство для работы - если вы сгенерировали 10 миллионов кодов, вам придется попробовать сотни тысяч комбинаций, чтобы перебрать код.

Или вы пришли с другого направления - укажите количество возможных кодов, сколько кодов должно вы сгенерируете, чтобы избежать ловушки, которую они называют Парадокс дня рождения

Принимая 8-значный код, 6 553 600 000 000 - это примерно 2 ⁴² , поэтому вы можете разумно сгенерировать из него 2 ²¹ кодов или 2 097 152

Answer 3

Как ни странно, с помощью следующего семени мне удалось сгенерировать только 32 уникальных строки.

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

С более длинным начальным числом я смог успешно сгенерировать гораздо больше - 40 000 уникальных строк.

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789

Answer 4

Какой бы метод вы ни использовали, я бы посоветовал вам добавить контрольную цифру или две в качестве «первой линии» защиты от людей, которые вводят или пытаются изобрести число.

Answer 5

Использовать алгоритм одноразового пароля?

RFC4225 детализирует один на основе алгоритма HMAC.

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

, но вместо кодировки base10 цифр 0-9 используйте base32.