Génération de nombres aléatoires non répétitifs en Python

Question

Ok, c'est une de ces questions plus délicates qu'il n'y paraît, je me tourne donc vers stack overflow parce que je n'arrive pas à trouver une bonne réponse. Voici ce que je veux : J'ai besoin de Python pour générer une simple liste de nombres de 0 à 1.000.000.000 dans un ordre aléatoire à utiliser pour les numéros de série (en utilisant un nombre aléatoire de sorte que vous ne pouvez pas dire combien ont été attribués ou faire des attaques de synchronisation aussi facilement, c'est-à-dire deviner le prochain qui va venir). Ces numéros sont stockés dans une table de base de données (indexée) avec les informations qui leur sont liées. Le programme qui les génère ne s'exécute pas éternellement et ne peut donc pas se fier à son état interne.

Ce n'est pas un gros problème, n'est-ce pas ? Il suffit de générer une liste de nombres, de les placer dans un tableau et d'utiliser Python "random.shuffle(big_number_array)" et le tour est joué. Le problème est que j'aimerais éviter d'avoir à stocker une liste de nombres (et donc de lire le fichier, d'en extraire un, de sauvegarder le fichier et de le fermer). Je préfère les générer à la volée. Le problème est que les solutions auxquelles je pense posent des problèmes :

1) Générer un numéro aléatoire et ensuite vérifier s'il a déjà été utilisé. S'il a été utilisé, générer un nouveau nombre, vérifier, répéter si nécessaire jusqu'à ce que je trouve un nombre inutilisé. Le problème ici est que je peux être malchanceux et générer un grand nombre de numéros utilisés avant d'en trouver un qui n'est pas utilisé. Solution possible : utiliser un très grand nombre de numéros pour réduire les risques (mais je me retrouve alors avec des numéros longs et stupides).

2) Générer un numéro aléatoire et ensuite vérifier s'il a déjà été utilisé. S'il a été utilisé, ajoutez ou soustrayez un au nombre et vérifiez à nouveau, répétez jusqu'à ce que je trouve un nombre inutilisé. Le problème est que ce n'est plus un nombre aléatoire car j'ai introduit un biais (je finirai par obtenir des groupes de nombres et vous serez en mesure de prédire le prochain nombre avec une meilleure chance de succès).

3) Générer un numéro aléatoire et vérifier ensuite s'il a déjà été utilisé. S'il a été utilisé, ajoutez ou soustrayez un autre nombre aléatoire généré et vérifiez à nouveau. Le problème est que nous revenons à la génération de nombres aléatoires et à la vérification comme dans la solution 1.

4) Se résigner à générer une liste aléatoire et la sauvegarder, demander à un démon de les mettre dans une file d'attente pour qu'il y ait des numéros disponibles (et éviter d'ouvrir et de fermer constamment un fichier, en le mettant en lot à la place).

5) Générer des nombres aléatoires beaucoup plus grands et les hacher (c'est-à-dire en utilisant MD5) pour obtenir une valeur numérique plus petite, nous devrions rarement avoir des collisions, mais je me retrouve à nouveau avec des nombres plus grands que nécessaire.

6) Ajoutez des informations temporelles au nombre aléatoire (par exemple, l'horodatage Unix) afin de réduire les risques de collision.

Quelqu'un a-t-il des idées astucieuses pour réduire les risques de "collision" (c'est-à-dire générer un numéro aléatoire qui est déjà pris) mais aussi pour me permettre de garder un nombre "petit" (c'est-à-dire inférieur à un milliard (ou mille millions pour vos Européens =)).

Réponse et pourquoi je l'ai acceptée :

Si c'est le cas, j'opterai pour la solution déterministe consistant à générer tous les nombres et à les stocker de manière à garantir l'obtention d'un nouveau nombre aléatoire, et je pourrai utiliser de "petits" nombres (c'est-à-dire 9 chiffres au lieu d'un MD5/etc.).

Answer 1

C'est un problème intéressant, et j'y ai réfléchi pendant un certain temps (avec des solutions similaires à Sjoerd's ), mais au final, voici ce que je pense :

Utilisez votre point 1) et arrêtez de vous inquiéter.

En supposant un caractère aléatoire réel, la probabilité qu'un nombre aléatoire ait déjà été choisi auparavant est le nombre de nombres précédemment choisis divisé par la taille de votre pool, c'est-à-dire le nombre maximal.

Si vous dites que vous n'avez besoin que d'un milliard de chiffres, c'est-à-dire 9 chiffres : Offrez-vous 3 chiffres supplémentaires, de sorte que vous ayez des numéros de série à 12 chiffres (c'est-à-dire trois groupes de quatre chiffres - agréables et lisibles).

Même lorsque vous êtes près d'avoir choisi un milliard de numéros auparavant, la probabilité que votre nouveau numéro soit déjà pris n'est encore que de 0,1%.

Faites l'étape 1 et dessinez à nouveau. Vous pouvez toujours vérifier qu'il n'y a pas de boucle "infinie", dire qu'il ne faut pas essayer plus de 1000 fois environ, puis revenir à l'étape 1 (ou autre).

Tu gagneras à la loterie avant que cette solution de repli ne soit utilisée.

Answer 2

Vous pourriez utiliser Cryptage avec préservation du format pour crypter un compteur. Votre compteur va simplement de 0 à plus, et le cryptage utilise une clé de votre choix pour le transformer en une valeur apparemment aléatoire de n'importe quel radix et largeur que vous voulez, qui est garantie de ne jamais avoir de collisions (parce que les algorithmes cryptographiques créent une correspondance 1:1).

L'un des avantages de ce système est qu'il est réversible. Vous pouvez donc prendre le numéro de série et le décrypter pour revenir à la simple valeur du compteur.

Les chiffrements par blocs ont normalement une taille de bloc fixe, par exemple 64 ou 128 bits. Mais le chiffrement avec préservation du format vous permet de prendre un chiffrement standard comme AES et d'en faire un chiffrement de plus petite largeur, avec le radix et la largeur que vous voulez. Par exemple, radix 10, largeur 9 pour les paramètres de la question. AES-FFX est une méthode standard proposée pour y parvenir. J'ai expérimenté avec un code Python de base pour AES-FFX voir le code Python ici . Il peut, par exemple, chiffrer un compteur en un nombre décimal à 7 chiffres d'apparence aléatoire.

Pour un autre exemple en Python, utilisant une autre méthode non-AES-FFX (je pense), voir Cet article de blog "Comment générer un numéro de compte". qui fait FPE en utilisant un chiffrement Feistel. Il génère des nombres de 0 à 2^32-1.

Answer 3

Avec un peu d'arithmétique modulaire et des nombres premiers, vous pouvez créer tous les nombres entre 0 et un grand nombre premier, dans le désordre. Si vous choisissez vos numéros avec soin, le numéro suivant est difficile à deviner.

modulo = 87178291199 # prime
incrementor = 17180131327 # relative prime

current = 433494437 # some start value
for i in xrange(1, 100):
    print current
    current = (current + incrementor) % modulo

Answer 4

Si vous n'avez pas besoin de quelque chose de cryptographiquement sûr, mais juste "suffisamment obscurci"...

Champs de Galois

Vous pouvez essayer des opérations dans Champs de Galois , par exemple GF(2) 32 pour mettre en correspondance un simple compteur incrémentiel x à un numéro de série apparemment aléatoire y :

x = counter_value
y = some_galois_function(x)

• Multiplier par une constante
  • L'inverse consiste à multiplier par l'inverse de la constante.
• S'élever à une puissance : x n
• Réciproque x -1
  • Cas particulier de l'élévation au pouvoir n
  • C'est son propre inverse
• Exponentiation d'un élément primitif : a x
  • Notez que cela n'a pas d'inverse facile à calculer (logarithme discret).
  • Assurer a es un élément primitif , alias générateur

Beaucoup de ces opérations ont un inverse, ce qui signifie qu'à partir de votre numéro de série, vous pouvez calculer la valeur originale du compteur dont il est issu.

Quant à trouver une bibliothèque pour les champs de Galois pour Python... bonne question. Si vous n'avez pas besoin de rapidité (ce qui n'est pas le cas pour cette application), vous pouvez créer la vôtre. Je n'ai pas essayé celles-ci :

• NZMATH
• Paquet Python pour les champs finis
• Sage mais il s'agit d'un environnement complet pour le calcul mathématique, bien plus qu'une simple bibliothèque Python.

Multiplication matricielle dans GF(2)

Choisissez une matrice inversible 32×32 appropriée dans GF(2), et multipliez un compteur d'entrée de 32 bits par celle-ci. Ceci est conceptuellement lié à LFSR, comme décrit dans La réponse de S.Lott .

CRC

Une possibilité connexe consiste à utiliser un CRC calcul. Basé sur le reste de la division longue avec un polynôme irréductible dans GF(2). Le code Python est facilement disponible pour les CRC ( crcmod , pycrc ), bien que vous puissiez choisir un polynôme irréductible différent de celui qui est normalement utilisé, pour vos besoins. Je suis un peu confus sur la théorie, mais je pense qu'un CRC 32 bits devrait générer une valeur unique pour chaque combinaison possible d'entrées de 4 octets. Vérifiez ceci. Il est assez facile de le vérifier expérimentalement, en réinjectant la sortie dans l'entrée et en vérifiant qu'elle produit un cycle complet de longueur 2. 32 -1 (zéro s'applique simplement à zéro). Il se peut que vous deviez vous débarrasser de tout XOR initial/final dans l'algorithme CRC pour que cette vérification fonctionne.

Answer 5

S'il n'est pas nécessaire qu'ils soient aléatoires, mais simplement non linéaires (1, 2, 3, 4, ...), voici un algorithme simple :

Choisissez deux nombres premiers. L'un d'eux sera le plus grand nombre que vous pouvez générer, il devrait donc être autour d'un milliard. L'autre devrait être assez grand.

max_value = 795028841
step = 360287471
previous_serial = 0
for i in xrange(0, max_value):
    previous_serial += step
    previous_serial %= max_value
    print "Serial: %09i" % previous_serial

Il suffit de mémoriser la série précédente à chaque fois pour savoir où vous vous êtes arrêté. Je ne peux pas prouver mathématiquement que cela fonctionne (cela fait trop longtemps que je n'ai pas suivi ces cours particuliers), mais c'est manifestement correct avec les petits nombres premiers :

s = set()
with open("test.txt", "w+") as f:
    previous_serial = 0
    for i in xrange(0, 2711):
        previous_serial += 1811
        previous_serial %= 2711
        assert previous_serial not in s
        s.add(previous_serial)

Vous pourriez également le prouver de manière empirique avec des nombres premiers à 9 chiffres, mais cela demanderait un peu plus de travail (ou beaucoup plus de mémoire).

Cela signifie qu'avec quelques numéros de série, il serait possible de déterminer vos valeurs - mais avec seulement neuf chiffres, il est peu probable que vous cherchiez à obtenir des chiffres indéchiffrables.