Question Comment fonctionne random ()?


Chaque langue a une fonction random () ou quelque chose de similaire pour générer un nombre pseudo-aléatoire. Je me demande ce qui se passe en dessous pour générer ces chiffres? Je ne programme rien qui rende cette connaissance nécessaire, essayant simplement de satisfaire ma propre curiosité.


13
2017-08-31 20:41


origine


Réponses:


Tout le premier chapitre du séminal de Donald Knuth  travail Algorithmes Séminériques est repris avec le sujet de la génération de nombres aléatoires. Je ne pense vraiment pas qu'une réponse SO puisse être proche de décrire les problèmes en cause. Lisez le livre.


12
2017-08-31 20:45



Il s'avère étonnamment facile d'obtenir des nombres pseudo-aléatoires à mi-chemin. Pendant des décennies, l'étalon-or était un algorithme remarquablement simple: X, multiplier par constante UNE (32x32 => 64 bits) puis ajouter constante B, puis retourner les 32 bits bas, qui deviennent également les nouveaux X. Si UNE et B sont choisis avec soin, cela fonctionne plutôt bien.

Les nombres pseudo-aléatoires doivent également être reproductibles pour reproduire le comportement lors du débogage. Donc, semer le générateur (initialisation X avec, disons, l'heure du jour) est généralement évité pendant le débogage.

Ces dernières années, et avec plus de cycles de calcul disponibles pour graver, des algorithmes plus sophistiqués sont disponibles, certains d’entre eux ayant été inventés Algorithmes Séminériques. Les systèmes d'exploitation commencent également à fournir du matériel et des bits d'entropie dérivés du réseau à des fins cryptographiques spécialisées.


4
2017-08-31 20:59



le Page Wikipedia est une bonne référence.

L'algorithme utilisé dépendra du langage et de l'implémentation du langage.


4
2017-08-31 20:46



random () est ce qu'on appelle un générateur de nombres pseudo-aléatoires (PRNG). random () est principalement implémenté comme un générateur congruentiel linéaire. Ceci est une fonction de la forme X (n + 1) (aXn + c) modulo m. Xn est la séquence des nombres pseudo-aléatoires générés. La séquence génarée des nombres est facile à deviner. Cet algorithme ne peut pas être utilisé comme un PRNG cryptographiquement sûr.

Wikipedia: Générateur linéaire congruentiel

Et jetez un coup d’œil aux tests extrêmes pour PRNG Tests PRNG Diehard


3
2017-08-31 20:54



Pour répondre exactement à votre réponse, la fonction aléatoire est fournie par le système d'exploitation (généralement).

Mais la façon dont le système d'exploitation crée ces nombres aléatoires est un domaine spécialisé en informatique. Voir par exemple la page du wiki publiée dans les réponses ci-dessus.


0
2017-08-31 20:49



Une chose que vous voudrez peut-être examiner est la famille de périphériques aléatoires disponibles sur certains systèmes d'exploitation de type Unix tels que Linux et Mac OSX. Par exemple, sous Linux, le noyau recueille de l'entropie à partir d'une variété de sources dans un pool qu'il utilise ensuite pour générer son générateur de nombres pseudo-aléatoires. L'entropie peut provenir de diverses sources, la plus notable étant la gigue des pilotes de périphériques à partir des pressions sur les touches, les événements réseau, l'activité du disque dur et (surtout) les mouvements de la souris. En dehors de cela, il existe d’autres techniques pour rassembler l’entropie, certaines étant même totalement implémentées dans le matériel. Il existe deux périphériques de caractères pour lesquels vous pouvez obtenir des octets aléatoires à partir de et sous Linux, ils se comportent de la manière suivante:

  • / dev / urandom vous donne un flux constant d'octets qui est très aléatoire mais pas sûr du point de vue cryptographique car il réutilise toute l'entropie disponible dans le pool.
  • / dev / random vous donne des nombres aléatoires sûrs du point de vue cryptographique, mais cela ne vous donnera pas un flux constant car il utilise l'entropie disponible dans le pool et bloque alors que plus d'entropie est collectée.

Notez que même si Mac OSX utilise une méthode différente pour son PRNG et ne bloque donc pas, mes tests personnels (réalisés en université) ont montré qu'il était légèrement moins aléatoire que le noyau Linux. Certainement assez bon, cependant.

Donc, dans mes projets, quand j'ai besoin de hasard, je vais généralement lire un des dispositifs aléatoires, du moins pour la graine d'un algorithme dans mon programme.


0
2017-09-01 00:55