Existe-t-il des générateurs de nombres aléatoires sans état?

Question

Existe-t-il une différence entre générer plusieurs numéros à l'aide d'un seul générateur de nombres aléatoires (RNG) et générer un nombre par générateur et le supprimer? Les deux implémentations génèrent-elles des nombres également aléatoires? Existe-t-il une différence entre les GNA normaux et les GNA sécurisés?

J'ai une application Web supposée générer une liste de nombres aléatoires pour le compte de clients. C'est-à-dire que les chiffres devraient paraître aléatoires du point de vue de chaque client. Est-ce que cela signifie que je dois conserver un RNG aléatoire distinct par session client? Ou puis-je partager un seul GNA pendant toutes les sessions? Ou puis-je créer et jeter un RNG à la demande?

MISE À JOUR : cette question concerne Un sous-ensemble d'une séquence aléatoire est-il également aléatoire?

Answer 1

Un générateur de nombres aléatoires a un état - c'est en fait une fonctionnalité nécessaire. Le prochain " aléatoire " numéro est une fonction du numéro précédent et de la graine / état. Les puristes les appellent des générateurs de nombres pseudo-aléatoires. Les nombres passeront des tests statistiques d’aléatoire, mais ne sont pas - en fait - aléatoires.

La séquence de valeurs aléatoires est finie et se répète.

Pensez à un générateur de nombre aléatoire comme en mélangeant une collection de nombres, puis en les distribuant dans un ordre aléatoire. La graine est utilisée pour "mélanger". les nombres. Une fois la graine établie, la séquence de chiffres est fixe et très difficile à prévoir. Certaines graines se répéteront plus tôt que d’autres.

La plupart des générateurs ont une période suffisamment longue pour que personne ne l’aperçoive de la répéter. Un générateur de nombre aléatoire de 48 bits produira plusieurs centaines de milliards de nombres aléatoires avant de se répéter - avec (autant que je sache) une valeur de départ de 32 bits.

Un générateur ne génère que des valeurs aléatoires lorsque vous lui donnez une seule graine et que vous le laissez cracher des valeurs. Si vous modifiez les valeurs de départ, les numéros générés avec la nouvelle valeur de valeur d'origine peuvent ne pas apparaître de manière aléatoire par rapport aux valeurs générées par la valeur d'origine - tous les paris sont désactivés lorsque vous modifiez les valeurs de départ. Alors ne le faites pas.

Une bonne approche consiste à avoir un générateur et un "accord". les chiffres autour de vos différents clients. Ne plaisante pas avec la création et la mise au rebut de générateurs. Ne plaisante pas avec le changement de semences.

Surtout, n'essayez jamais d'écrire votre propre générateur de nombres aléatoires. Les générateurs intégrés dans la plupart des bibliothèques de langues sont vraiment bons. Surtout ceux modernes qui utilisent plus de 32 bits.

Certaines distributions Linux ont un périphérique / dev / random et / dev / urandom . Vous pouvez les lire une fois pour créer le générateur de nombres aléatoires de votre application. Celles-ci ont des valeurs plus ou moins aléatoires, mais elles fonctionnent en "rassemblant le bruit". à partir d'événements aléatoires du système. Utilisez-les avec parcimonie afin qu'il y ait beaucoup d'événements aléatoires entre les utilisations.

Answer 2

Je recommanderais d'utiliser un seul générateur plusieurs fois. Autant que je sache, tous les générateurs ont un état. Lorsque vous générez un générateur, vous définissez son état sur quelque chose basé sur la graine. Si vous en créez de nouveaux, il est probable que les graines que vous sélectionnerez ne seront pas aussi aléatoires que les nombres générés en utilisant un seul générateur.

Cela est particulièrement vrai avec la plupart des générateurs que j'ai utilisés, qui utilisent l'heure actuelle en millisecondes comme une graine.

Answer 3

Les générateurs de nombres aléatoires basés sur le matériel, vrais [1], sont possibles, mais non triviaux et ont souvent des taux moyens bas. La disponibilité peut également être un problème [2]. Googler pour " coup de feu " ou "décroissance radioactive" en combinaison avec " générateur de nombres aléatoires " devrait renvoyer des résultats.

Ces systèmes n'ont pas besoin de conserver l'état. Probablement pas ce que vous cherchiez.

Comme d'autres l'ont noté, les systèmes logiciels ne sont que pseudo-aléatoires et doivent conserver leur état.

Un compromis consiste à utiliser un GNA basé sur le matériel pour fournir un pool d'entropie (état stocké) qui est mis à disposition pour générer un PRNG. Ceci est fait assez explicitement dans les implémentations sous Linux de / dev / random [3] et / dev / urandom [4].

Ceci est un argument sur le fait que les entrées par défaut du pool d'entropie / dev / random sont vraiment aléatoires.

Notes de bas de page:

1. modulo aucun problème avec notre compréhension de la physique
2. parce que vous attendez un processus aléatoire
3. / dev / random propose un accès direct au pool d'entropie provenant de diverses sources supposées être réellement ou presque aléatoires, et se bloque lorsque l'entropie est épuisée
4. / dev / urandom est semblable à / dev / random, mais lorsque l'entopie est épuisée, un hachage cryptographique est utilisé, ce qui fait du pool d'entropie un PRNG avec état

Answer 4

Si vous créez un RNG et générez un nombre aléatoire à partir de celui-ci, puis supprimez le RNG, le nombre généré est aussi aléatoire que la valeur initiale utilisée pour démarrer le RNG.

Il serait bien préférable de créer un seul GNA et d'en tirer de nombreux nombres.

Answer 5

Comme on l’a déjà dit, il est bien préférable de semer le PRNG une fois et de le réutiliser. Un PRNG sécurisé convient tout simplement aux applications cryptographiques. Le seul moyen de réensemencer chaque fois donnera des résultats raisonnablement aléatoires, c’est là où il provient d’un "monde réel" véritablement aléatoire. source - c.-à-d. matériel spécialisé. Même dans ce cas, il est possible que la source soit biaisée et il sera théoriquement préférable d’utiliser le même PRNG.

Answer 6

Normalement, créer un nouvel État prend un certain temps, mais en créer de nouveaux à chaque fois n’aidera pas grand-chose. Le seul cas auquel je puisse penser où vous voudrez peut-être plus d'un PRNG concerne différents systèmes, par exemple, dans un jeu de casino, vous disposez d'un générateur pour mélanger les cartes et d'un autre pour générer les commentaires des personnages de contrôle de l'ordinateur, ainsi dédiés VRAIMENT les utilisateurs ne peuvent pas deviner les résultats basés sur les comportements des personnages.

Une bonne solution pour semer consiste à utiliser this (Random.org) , car ils fournissent des données aléatoires. nombres générés gratuitement à partir du bruit atmosphérique. Ce pourrait être une meilleure source d'ensemencement que d'utiliser le temps.

Éditer: Dans votre cas, j’utiliserais certainement un PRNG par client, ne serait-ce que pour de bonnes normes de programmation. Quoi qu'il en soit, si vous partagez un PRNG entre plusieurs clients, vous continuerez à fournir à chacun des valeurs pseudo-aléatoires, d'une qualité égale à celle de votre PRNG. Donc, c’est une option viable mais cela semble être une mauvaise politique de programmation

Answer 7

Il convient de mentionner que Haskell est un langage qui tente d’éliminer complètement les états mutables. Afin de concilier cet objectif avec des exigences strictes telles que l'IO (qui requiert une forme de mutabilité), les monades doivent être utilisées pour passer d'un calcul à l'autre. De cette façon, Haskell implémente son générateur de nombres pseudo-aléatoires. À proprement parler, la génération de nombres aléatoires est une opération intrinsèquement dynamique, mais Haskell peut masquer ce fait en déplaçant l'état "mutation". dans l'opération bind ( > > = = ).

Cela semble probablement un peu abstrait, et cela ne répond pas vraiment à votre question, mais je pense que cela reste applicable. D'un point de vue théorique, il est impossible de travailler avec un RNG sans impliquer un état. Quoi qu’il en soit, il existe des techniques qui peuvent être utilisées pour atténuer cette interaction et lui donner l’apparence comme si l’opération entière avait un caractère sans état.

Answer 8

Il est généralement préférable de créer un seul PRNG et d’en extraire plusieurs valeurs. La création de plusieurs instances signifie que vous devez vous assurer que les germes des instances sont uniques, ce qui nécessitera l'incorporation d'informations spécifiques à l'instance.

En passant, il y a mieux "vrai". Les générateurs de nombres aléatoires, mais ils nécessitent généralement un matériel spécialisé permettant, par exemple, de dériver des données aléatoires à partir de la variance des signaux électriques à l'intérieur de l'ordinateur. À moins que cela ne vous inquiète vraiment, je dirais que les générateurs de nombres pseudo-aléatoires intégrés aux bibliothèques de langues et / ou au système d'exploitation sont probablement suffisants, tant que votre valeur de départ n'est pas facilement prévisible.

Answer 9

L'utilisation d'un PRNG sécurisé dépend de votre application. A quoi servent les nombres aléatoires? S'ils ont une valeur réelle (par exemple, tout ce qui est lié à la cryptographie), vous ne voudriez rien utiliser de moins.

Les PRNG sécurisés sont beaucoup plus lents et peuvent nécessiter que les bibliothèques effectuent des opérations de précision arbitraire, des tests de primalité, etc., etc.

Answer 10

Eh bien, tant qu’ils sont ensemencés différemment chaque fois qu’ils sont créés, alors non, je ne pense pas qu’il y aurait une différence; Cependant, si cela dépendait de quelque chose comme le temps, ils seraient probablement non uniformes, en raison de la présence de graines biaisées.