Создание уникальных кодов в PHP / MySQL?

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

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


mysql php random generator serial-number
person Eaton    schedule 20.10.2008    source источник

Ответы (5)


arrow_upward
13
arrow_downward

Если вам нужно около 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;
}
person ojrac    schedule 20.10.2008
comment
Моя цель состояла в том, чтобы избежать этого специально, чтобы вам не нужно было выполнять проверку уникальности для каждой отдельной строки во время INSERT. Вместо этого вы можете вставить полный список данных и отсортировать его один раз за O (n lg n). Если БД не проверяет ваш уникальный ключ менее чем за O (lg n), вам нужна неиндексированная БД. - person ojrac; 21.10.2008

arrow_upward
7
arrow_downward

Предположим, вы можете использовать набор символов, состоящий, например, из 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 символов дают довольно хорошее пространство для работы - если вы сгенерировали 10 миллионов кодов, вам придется попробовать сотни тысяч комбинаций, чтобы перебрать код.

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

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

person Paul Dixon    schedule 20.10.2008

arrow_upward
0
arrow_downward

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

RFC4225 подробно описывает один, основанный на алгоритме HMAC.

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

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

person Community    schedule 20.10.2008

arrow_upward
0
arrow_downward

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

person staticsan    schedule 30.10.2008

arrow_upward
-3
arrow_downward

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

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

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

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ267592345678

person kalinma    schedule 28.08.2009