two - ¿Generando códigos únicos en PHP/MySQL?

select random mysql

Question

Estoy trabajando con un cliente que necesita generar millones de códigos alfanuméricos utilizados en tarjetas raspables de revistas, premios en tapas de botellas, etc. Deben ser lo suficientemente cortos como para imprimir en un límite, quieren asegurarse de que los caracteres ambiguos como 1 y I, 0 y O, etc. no estén incluidos, y deben almacenarse explícitamente para su uso futuro, podemos '' Solo tengo un algoritmo que determina la "validez" cuando alguien intenta canjear uno. Finalmente, quieren asegurarse de que los códigos se distribuyan al azar dentro de un gran "espacio de código" para que las personas no puedan adivinar códigos adicionales caminando por el alfabeto.

¿Hay algún indicador de algoritmos razonablemente eficientes para generar este tipo de conjuntos de códigos? He arañado algunas en el reverso de un sobre, pero este problema huele a trampa para los incautos.

Answer 1

Si necesita aproximadamente 10 millones de claves únicas (por ejemplo), el mejor enfoque es elegir un espacio clave que sea exponencialmente más grande y comenzar a generar aleatoriamente. Lea sobre la paradoja del cumpleaños : es lo principal de lo que debería preocuparse. Si quiere 2 ^ n claves únicas y seguras, asegúrese de que haya al menos 2 ^ (2 * n) valores posibles. Aquí hay un algoritmo aproximado O (n log n):

• Use un espacio de clave de al menos 2 ^ 50 (por lo tanto, en otras palabras, permita 2 ^ 50 valores únicos posibles), y apenas tendrá colisiones en todo su conjunto de datos, y cualquier persona que forme sus llaves tendrá incluso un equilibrio probabilidades de obtener una clave si intentan 2 ^ 25 de ellas.
• generar tantos números aleatorios como sea necesario
• indexe la base de datos en su clave (este es el paso O (n lg n): el tipo)
• página a través de la base de datos e iterar sobre todo el conjunto de datos para recortar duplicados (pseudocódigo a continuación)
• Eliminar las filas duplicadas, y listo.

Pseudocódigo:

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

Answer 2

Use un algoritmo de contraseña de una vez?

RFC4225 detalla uno basado en el algoritmo HMAC.

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

pero en lugar de usar 0-9 digits base10 encoding, usa base32.

Answer 3

Cualquiera que sea el método que use, le sugiero que agregue un dígito de control o dos como una defensa de "primera línea" contra personas que ingresan incorrectamente o intentan inventar un número.

Answer 4

Por extraño que parezca, con la siguiente semilla solo pude generar 32 cadenas únicas.

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

Con una semilla más larga, pude generar muchas más: generé 40,000 cadenas únicas con éxito.

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789

Answer 5

Supongamos que puede usar un juego de caracteres de, digamos, 40 símbolos de caracteres superiores, inferiores y numéricos inequívocos.

Para una secuencia de n caracteres, tienes 40 ⁿ combinaciones

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

Por lo tanto, 8 caracteres proporcionan un espacio bastante bueno para trabajar; si generara 10 millones de códigos, tendría que probar cientos de miles de combinaciones para generar un código de fuerza bruta.

O vienes desde la otra dirección: da la cantidad de códigos posibles , ¿cuántos códigos deberías generar para evitar la trampa que llaman la paradoja del cumpleaños ?

Tomando el código de 8 caracteres, 6,553,600,000,000 es aproximadamente 2 ⁴² , por lo que puede generar razonablemente 2 ²¹ códigos a partir de él, o 2,097,152