Pourquoi est-il impossible de produire des nombres vraiment aléatoires?

J'essayais de résoudre un problème de loisir qui nécessitait la génération d'un million de nombres aléatoires. Mais je me suis vite rendu compte qu'il devenait difficile de les rendre uniques. J'ai pris Algorithm Design Manual pour en savoir plus sur la génération de nombres aléatoires.

Il contient le paragraphe suivant que je ne suis absolument pas capable de comprendre.

Malheureusement, générer des nombres aléatoires semble beaucoup plus facile qu’il ne l’est réellement. En effet, il est fondamentalement impossible de produire des nombres véritablement aléatoires avec un appareil déterministe. Von Neumann [Neu63] a dit le mieux: «Quiconque considère des méthodes arithmétiques pour produire des chiffres aléatoires est, bien sûr, dans un état de péché.» Le mieux que nous puissions espérer est un nombre pseudo-aléatoire, si elles ont été générées aléatoirement.

Pourquoi est-il impossible de produire des nombres véritablement aléatoires dans un appareil déterministe? Que signifie cette phrase?

On devrait rechercher un générateur de nombres pseudo-aléatoires cryptographiquement sécurisé . La plupart PRNG sont générateurs de congruence linéaires (donc next numberest une fonction linéaire de previous number), donc si vous tracer next numbervs previous numbervous obtiendrez un tableau de lignes parallèles. Un CSPRNG ne fera pas cela. Le compromis est qu'ils sont lents.

Je groupe les générateurs de nombres aléatoires en 3 catégories :

1. Assez bon pour les devoirs.
2. Assez bon pour parier votre compagnie.
3. Assez bon pour parier votre pays.

Pourquoi est-il impossible de produire des nombres véritablement aléatoires dans un appareil déterministe?

Un appareil déterministe produira toujours la même sortie lorsque les mêmes conditions de démarrage et les mêmes entrées sont remplies - c'est ce que cela signifie deterministic. "Nombre véritablement aléatoire" est plutôt un point de vue philosophique, car ce que cela signifie, randomc'est le coeur du regard philosophique sur le nombril (les gens ne savent même pas si la désintégration atomique est aléatoire ou suit un modèle que nous ne pouvons tout simplement pas comprendre. encore). Un générateur de nombres aléatoires cryptographiquement sécurisé utilisera une source d'entropie externe pour rendre le dispositif non déterministe.

Le vrai hasard implique le non déterminisme. Si c'est déterministe, on peut le prédire avec précision (c'est ce que le déterminisme signifie); si on peut le prédire, ce n'est pas aléatoire.

La meilleure chose que vous puissiez obtenir d’un générateur de nombres pseudo-aléatoires déterministes est un flux de nombres qui a un cycle très long (il est impossible de répéter l'opération, sauf si votre dispositif RNG dispose d'une mémoire de stockage illimitée) qui, pour la longueur du cycle, produit une numéros de flux qui répondent à toutes les autres propriétés d'une séquence aléatoire (une distribution uniforme de valeurs étant la plus intéressante).

Pour résoudre ce problème, de nombreux UNIX modernes et similaires à Unix ont des RNG de noyau qui utilisent des sources de bruit physiques pour générer un véritable caractère aléatoire.

Une autre approche courante consiste à prendre l’heure actuelle comme germe pour un GNR déterministe ( srand(time(NULL));en C); cryptographiquement parlant, cela n’a aucune valeur, car l’heure actuelle n’est pas un secret, mais il vous suffit pour des choses comme les simulations physiques ou les jeux vidéo.

Le deuxième chapitre du livre Simulation à événements discrets: un premier cours de Lawrence Leemis est une introduction fantastique aux générateurs de nombres aléatoires (ou plus précisément, aux générateurs de nombres aléatoires pseudo-aléatoires).

Un extrait de son livre l'explique bien à mon avis:

Historiquement, trois types de générateurs de nombres aléatoires ont été préconisés pour les applications informatiques: (a) des générateurs de recherche de table de style années 1950, tels que, par exemple, la table de sociétés RAND d'un million de chiffres aléatoires; (b) des générateurs matériels tels que, par exemple, des dispositifs thermiques à "bruit blanc"; et (c) des générateurs algorithmiques (logiciels). De ces trois types, seuls les générateurs algorithmiques ont été largement acceptés. La raison en est que seuls les générateurs algorithmiques ont le potentiel de satisfaire à tous les critères de génération de nombres aléatoires généralement bien acceptés suivants. Un générateur devrait être:

• random - capable de produire une sortie qui passe tous les tests statistiques raisonnables du caractère aléatoire;
• contrôlable - capable de reproduire sa sortie, si désiré;
• portable - capable de produire le même résultat sur une grande variété de systèmes informatiques;
• efficace - rapide, avec des besoins en ressources informatiques minimaux;
• documenté - théoriquement analysé et testé de manière approfondie.

Ainsi, bien qu'il soit possible d'utiliser un générateur de bruit blanc pour obtenir de "meilleurs" nombres aléatoires, ils n'ont pas été acceptés, car ils ne respectent pas la plupart des critères ci-dessus.

Je vous recommanderais de mettre la main sur un exemplaire de ce livre (ou quelque chose de similaire). Comprendre exactement comment le travail de PRNG vous aidera dans vos efforts.

Parce que vous devez écrire du code pour générer les nombres aléatoires et que Code n'est PAS aléatoire. (C'est déterministe)

Vous commencez donc par une "valeur de départ" sélectionnée sur "Aléatoire" (généralement l'horodatage actuel), puis vous l'utilisez dans un algorithme pour commencer à générer des nombres. Mais l'ensemble de est basé sur la valeur d'origine de la graine!

Donc, si vous exécutez à nouveau votre code avec la même valeur de semences, vous obtiendrez le même ensemble de chiffres EXACT! Comment une personne raisonnable peut-elle appeler cela au hasard? Mais il ne vous REGARD au hasard.

Pour ce qui est de les rendre uniques, après avoir généré un numéro, vérifiez simplement si vous avez déjà ce numéro, le cas échéant, jetez-le et générez-en un nouveau.

Puisque vous générez des nombres aléatoires, vous devez vous attendre à ce que les valeurs générées soient non uniques. Ceci est une propriété du hasard - vous ne pouvez pas dire qu'une séquence de nombres vraiment aléatoires (ou même pseudo-aléatoires) est unique, car cette exigence permettrait de prédire la valeur finale dans la plage, ainsi que de modifier la probabilité de tous les numéros non choisis chaque fois qu'un nouveau est sélectionné.

J'ai une définition très simple de pseudo-aléatoire :

Trop de variables inconnues à prédire.

J'ai aussi une définition simple de True Random :

Variables inconnues infinies.

Le problème avec un ordinateur est qu’il connaît toujours TOUTES les variables. Le nombre aléatoire est simplement une fonction mathématique d'une valeur de départ .
Le mieux que nous puissions faire est de donner à l'ordinateur une valeur de départ pseudo-aléatoire, généralement basée sur une variable que nous ne pouvons pas prédire (telle que l'heure exacte).

Même si un ordinateur est absolument incapable de créer un nombre aléatoire, il est bon pour introduire trop de variables à prévoir!

La génération de nombres réellement aléatoires dans le logiciel n’est en effet pas possible, comme d’autres l'ont déjà souligné, mais il est possible avec un matériel informatique de créer un dispositif capable de générer des nombres réellement aléatoires *. Il existe de nombreux exemples de ce type sur Internet, et diverses méthodes sont utilisées, allant de la lecture du compteur Geiger entre les ticks et à l’échantillonnage du bruit blanc (principalement le rayonnement de fond de l’univers) d’un récepteur non accordé. J'ai moi-même construit quelques-unes en utilisant quelques-unes des méthodes disponibles.

* Tout bon connaisseur en physique remarquera que, compte tenu de la façon dont l’univers fonctionne, aucun de ceux-ci n’est hyper-technique, mais il n’existe aucun moyen raisonnable de prédire les résultats.

Il n’ya aucun moyen de produire un nombre aléatoire sans matériel spécial. Lors de ma première année, quelques camarades de classe et moi avons proposé un générateur de nombres aléatoires doté d'un récepteur AM et syntonisé sur 4 canaux différents, permettant l'entrée dans un convertisseur A / N et les ajoutant tous (modulo votre nombre maximum). Étant donné que la combinaison des entrées analogiques provenant de tout nombre arbitraire de stations est aléatoire et que nous pourrions produire un grand nombre de nombres aléatoires à partir du convertisseur A2D, nous proposons qu'il s'agisse d'un bon générateur. Bien sûr, même cela n’est pas vraiment aléatoire au sens philosophique du terme, bien que cela puisse fonctionner dans la plupart des cas.

Le déterminisme est essentiellement une fonction. Rappelez-vous d'Algèbre qu'une fonction est une correspondance entre un domaine et une plage telle que chaque membre du domaine corresponde exactement à un membre de la plage.

Donc, si f (x) = z, f (x)! = Y sauf si y est z. C'est une fonction. Imaginez JavaScript:

function Add(A, B) {
      return A + B;
}

var addedNumber = Add(2,3);//returns 5
addedNumber = Add(2,3);//still 5

Peu importe le nombre de fois que vous appelez, Add(2,3)le résultat sera toujours 5. En d'autres termes, Add () est une fonction déterministe.

Des facteurs externes peuvent faire en sorte que Add se comporte de manière non déterministe. Par exemple, si vous introduisez le multithreading dans l'équation. L'apport humain provoque également le non-déterminisme.

Maintenant, c’est là que les choses deviennent intéressantes.

"Quiconque considère des méthodes arithmétiques pour produire des chiffres aléatoires est, bien sûr, dans un état de péché."

Remarque Von Neumann déclare "des méthodes arithmétiques de production [...]". Il ne s'agit pas d'entrée humaine, de simultanéité, de vitesses de vent échantillonnées lues à partir d'un instrument précis ou d'autres moyens non algorithmiques de produire une entrée aléatoire pour une fonction déterministe.

Cela indique simplement qu'une fonction ou un système de fonctions ne va pas devenir soudainement non déterministe. En d'autres termes, Add (2,3) ne retournera pas 6 ou autre chose que 5 avec les mêmes entrées . C'est impossible.

L'auteur citant va encore plus loin.

Le mieux que nous puissions espérer est un nombre pseudo-aléatoire, un flot de nombres qui apparaissent comme s'ils avaient été générés aléatoirement.

Le contexte est précédemment défini comme étant "sur tout dispositif déterministe". Je pourrais mettre fin à la discussion ici. Mais que se passe-t-il si nous modifions le contexte en introduisant un nouvel élément dans le système? Un élément non déterministe ajouté en entrée fait du système un système non déterministe. Bien que, en supprimant l'élément non déterministe, nous sommes réduits à un système déterministe. Si nous pouvons en quelque sorte tracer ou reproduire les entrées, nous pouvons reproduire un résultat. Mais tout ce paragraphe correspond à ce que dit l'auteur. Rappelez-vous le contexte.

On pourrait discuter du sens du non-déterminisme. Encore une fois, tangetenial. Rappelez-vous le contexte.

Alors il a raison. Quel que soit le dispositif déterministe, il est impossible pour un système déterministe de produire un véritable résultat aléatoire.