Qu'est-ce qui fait qu'un générateur pseudo-aléatoire est de haute qualité?

8

En lisant cette réponse à cette question SO: Pourquoi ne combinons-nous pas des générateurs de nombres aléatoires? , ça parle de

PRNG de très haute qualité (Pseudo Random Number Generator)

donc je me demande ce qui constitue un PRNG de haute qualité, je suppose que vous pouvez le résumer comme étant "plus aléatoire", mais

  • Question 1: Quelles qualités d'un PRNG sont utilisées pour décrire à quel point il est «aléatoire» ou «bon»?

  • Question 2: Si vous avez un PRNG de «mauvaise qualité», existe-t-il un moyen de le rendre de meilleure qualité?

randomness pseudo-random-generators random-number-generator Jose
la source
Pertinentes stackoverflow.com/questions/2130621/...
Adriann
2
Vous devez également distinguer les PRNG banals des RNG sécurisés cryptographiquement.
adrianN
1
Un PRNG est «meilleur» s'il est plus difficile de distinguer sa sortie de bits complètement aléatoires.
Yuval Filmus

Réponses:

9

Il existe plusieurs critères pour la qualité d'un PRNG:

  • Comme c'est rapide. Cela inclut la rapidité avec laquelle il est configuré et la vitesse avec laquelle il produit un seul bit (amorti).
  • Il est difficile de deviner le bit suivant étant donné tous les bits précédents.
  • Il est difficile de distinguer la sortie du PRNG des bits vraiment aléatoires.

Les deux derniers critères sont fortement liés.

Si vous avez un PRNG de mauvaise qualité, vous pouvez souvent l'améliorer par amplification de dureté . Prenez plusieurs copies du PRNG (en utilisant différentes clés aléatoires) et XOR ensemble. Dans de nombreux cas (mais pas tous), cela améliorera considérablement sa qualité.

Yuval Filmus
la source
Juste une autre question: pourquoi utiliser un PRNG qui provoquera la même séquence si la même graine est utilisée deux fois, et pas seulement obtenir une nouvelle graine (horloge cpu par exemple) chaque fois qu'un nouveau nombre aléatoire est nécessaire? cette approche ne serait-elle pas plus aléatoire?
Jose
2
@Jose C'est par conception. Dans de nombreux cas, vous voulez pouvoir générer plusieurs fois la même séquence exacte. Deux exemples sont les expériences de Monte Carlo (qui devraient être répétables) et la cryptographie (où nous voulons que deux utilisateurs possèdent la même séquence aléatoire, utilisée comme clé).
Yuval Filmus
Les expériences de Monte Carlo ont rarement besoin d'un PRNG cryptographique.
Xavier Combelle
2

Il y a des considérations pratiques: comment facile à utiliser? À quelle vitesse? Est-il facile de produire une séquence différente de nombres aléatoires? Est-il facile de rejouer les nombres aléatoires (par exemple, si vous avez généré 10 milliards de nombres aléatoires, pouvez-vous générer à nouveau exactement les mêmes 10 milliards de nombres aléatoires?)

La grande question: les nombres générés se comportent-ils comme une séquence de nombres aléatoires? Le premier PRNG que j'ai jamais utilisé avait la propriété bizarre de deux valeurs consécutives, la seconde était plus grande avec une probabilité d'environ 0,6. Pas très aléatoire. Vous pouvez donc exécuter toutes sortes de tests statistiques et vérifier si votre générateur de nombres aléatoires se comporte de manière aléatoire. Plus il se comporte comme aléatoire, mieux c'est.

Et puis vient le hasard cryptographique. Si je vous donne les n derniers nombres aléatoires et que je connais parfaitement le comportement du générateur de nombres aléatoires, pouvez-vous prédire le prochain nombre aléatoire? Si oui, cela le rend inapproprié dans les situations où vous avez des adversaires.

gnasher729
la source
0

J'ajouterais une distribution uniforme à la liste des qualités souhaitées.

Maciek Łoziński
la source
Il est généralement entendu qu'un PRNG génère une distribution uniforme (ou presque).
vonbrand