Un type a dit ce qui suit:

Quiconque tente de générer des nombres aléatoires par des moyens déterministes vit, bien sûr, dans un état de péché.

Cela signifie toujours que vous ne pouvez pas générer de vrais nombres aléatoires avec juste un ordinateur. Et il a dit que lorsque les ordinateurs étaient de la taille équivalente à un seul microprocesseur Intel 8080 (~ 6000 valves). Les ordinateurs sont devenus plus complexes et je pense que la déclaration de von Von Neumann n'est peut-être plus vraie. Considérez qu'un algorithme uniquement logiciel implémenté est impossible. Ils fonctionnent sur du matériel physique. Les véritables générateurs de nombres aléatoires et leurs sources d'entropie sont également constitués de matériel.

Ce fragment Java mis en boucle:

      file.writeByte((byte) (System.nanoTime() & 0xff));

peut créer un fichier de données que j'ai représenté comme une image:

Vous pouvez voir la structure, mais aussi avec beaucoup d'aléatoire. Ce qui est intéressant, c'est que ce fichier PNG est de 232 Ko, mais contient 250 000 pixels d'échelle de gris. Le niveau de compression PNG était maximum. Ce n'est qu'un taux de compression de 7%, c'est-à-dire. assez non compressible. Ce qui est également intéressant, c'est que le fichier est unique. Chaque génération de ce fichier est un modèle légèrement différent et a une compressibilité similaire à ~ 7%. Je souligne cela car il est essentiel à mon argument. C'est une entropie d'environ 7 bits / octet. Cela réduira bien sûr l'utilisation d'un algorithme de compression plus puissant. Mais pas réduire à quelque chose près de 0 bits / octet. Une meilleure impression peut être obtenue en prenant l'image ci-dessus et en remplaçant sa carte de couleurs par une image aléatoire: -

La majeure partie de la structure (dans la moitié supérieure) disparaît car il ne s'agissait que de séquences de valeurs similaires mais légèrement différentes. Est-ce une véritable source d'entropie créée en exécutant simplement un programme Java sur un système d'exploitation à prises multiples? Pas un générateur de nombres aléatoires uniformément distribué, mais la source d'entropie pour un? Une source d'entropie constituée de logiciels fonctionnant sur du matériel physique qui se trouve être un PC.

Supplémentaire

Afin de confirmer que chaque image génère une nouvelle entropie sans motif fixe commun à tous, 10 images consécutives ont été générées. Celles-ci ont ensuite été concaténées et compressées avec l'archiveur le plus puissant que j'ai pu compiler (paq8px). Ce processus éliminera toutes les données courantes, y compris la corrélation automatique, ne laissant que les changements / l'entropie.

Le fichier concaténé est compressé à ~ 66%, ce qui conduit à un taux d'entropie de ~ 5,3 bits / octet ou 10,5 Mbits / image. Une quantité surprenante d'entropie$\smile$

Supplémentaire 2

Il y a eu des commentaires négatifs selon lesquels ma méthode de test d'entropie par compression est défectueuse, ne donnant qu'une estimation de la limite supérieure lâche. J'ai donc exécuté le fichier concaténé via le test officiel d'évaluation de l'entropie cryptographique du NIST, SP800-90B_EntropyAssessment . C'est aussi bon que pour la mesure d'entropie non IID. Voici le rapport (désolé, cette question devient longue, mais le problème est complexe): -

Running non-IID tests...

Entropic statistic estimates:
Most Common Value Estimate = 7.88411
Collision Test Estimate = 6.44961
Markov Test Estimate = 5.61735
Compression Test Estimate = 6.65691
t-Tuple Test Estimate = 7.40114
Longest Reapeated Substring Test Estimate = 8.00305

Predictor estimates:
Multi Most Common in Window (MultiMCW) Test: 100% complete
    Correct: 3816
    P_avg (global): 0.00397508
    P_run (local): 0.00216675
Multi Most Common in Window (Multi MCW) Test = 7.9748
Lag 

Test: 100% complete
    Correct: 3974
    P_avg (global): 0.00413607
    P_run (local): 0.00216675
Lag Prediction Test = 7.91752
MultiMMC Test: 100% complete
    Correct: 3913
    P_avg (global): 0.00407383
    P_run (local): 0.00216675
Multi Markov Model with Counting (MultiMMC) Prediction Test = 7.9394
LZ78Y Test: 99% complete
    Correct: 3866
    P_avg (global): 0.00402593
    P_run (local): 0.00216675
LZ78Y Prediction Test = 7.95646
Min Entropy: 5.61735

Le résultat est que le NIST pense que j'ai généré 5,6 bits / octet d'entropie. Mon estimation de la compression bricolage met cela à 5,3 bits / octet, légèrement plus conservateur.

-> Les preuves semblent soutenir l'idée qu'un ordinateur exécutant simplement un logiciel peut générer une véritable entropie. Et que von Neumann avait tort (mais peut-être correct pour son époque).

J'offre les références suivantes qui pourraient soutenir ma réclamation: -

Existe-t-il des modèles stochastiques de non déterminisme dans le taux d'exécution du programme?

Analyse WCET des systèmes probabilistes en temps réel dur

Existe-t-il un algorithme logiciel qui peut générer un modèle de chaos non déterministe? et la pertinence des effets chaotiques.

Parallèles avec le principe d'incertitude entropique quantique

Article de blog d' Aleksey Shipilёv concernant le comportement chaotique de nanoTime (). Son nuage de points n'est pas différent du mien.

Le fait que vous ne puissiez pas voir un motif ne signifie pas qu'aucun motif n'existe. Ce n'est pas parce qu'un algorithme de compression ne trouve pas de motif qu'il n'y a pas de motif. Les algorithmes de compression ne sont pas des balles d'argent qui peuvent magiquement mesurer la véritable entropie d'une source; tout ce qu'ils vous donnent est une limite supérieure de la quantité d'entropie. (De même, le test NIST ne vous donne également qu'une limite supérieure.) Le chaos n'est pas aléatoire.

Il faut une analyse et un examen plus détaillés pour commencer à avoir une certaine confiance dans la qualité du caractère aléatoire obtenu de cette manière.

Il y a des raisons de penser que nous pouvons probablement obtenir une certaine quantité d'aléatoire en exploitant la gigue d'horloge et la dérive entre deux horloges matérielles , mais c'est délicat et délicat, vous devez donc être prudent. Je ne recommanderais pas d'essayer de mettre en œuvre le vôtre. Au lieu de cela, je vous suggère d'utiliser une source d'entropie de haute qualité (généralement implémentée dans la plupart des systèmes d'exploitation modernes). Pour plus de détails, voir également Wikipedia , haveged et /crypto//q/48302/351 (dont il semble que vous soyez déjà au courant).

Enfin, un commentaire sur votre ouvreur:

"Quiconque tente de générer des nombres aléatoires par des moyens déterministes vit, bien sûr, dans un état de péché."

Cela signifie toujours que vous ne pouvez pas générer de vrais nombres aléatoires avec juste un ordinateur.

Non, ce n'est pas comme cela que l'on prend habituellement, et ce n'est pas ce qu'il dit. Cela signifie que vous ne pouvez pas générer de vrais nombres aléatoires par des moyens déterministes . Que vous puissiez le faire sur un ordinateur dépend du fait que l'ordinateur soit déterministe ou non. Si l'ordinateur est déterministe ou si votre programme n'utilise que des opérations déterministes, vous ne pouvez pas. Cependant, de nombreux ordinateurs contiennent des éléments non déterministes et si votre programme les utilise, une analyse plus détaillée est nécessaire avant de pouvoir décider s'ils peuvent être utilisés pour générer des nombres aléatoires. Dans votre cas, ce nanoTime()n'est pas déterministe.

Si vous utilisez une source matérielle d'entropie / caractère aléatoire, vous n'essayez pas de «générer du caractère aléatoire par des moyens déterministes » (c'est moi qui souligne). Si vous n'utilisez aucune source matérielle d'entropie / aléatoire, un ordinateur plus puissant signifie simplement que vous pouvez commettre plus de péchés par seconde.

J'ai toujours compris que la citation signifie qu'un algorithme déterministe a une quantité fixe d'entropie, et bien que la sortie puisse apparaître "aléatoire", elle ne peut pas contenir plus d'entropie que les entrées ne le fournissent. Dans cette perspective, nous voyons que votre algorithme passe en contrebande via l'entropie System.nanoTime()- la plupart des définitions d'un algorithme «déterministe» interdiraient d'appeler cette fonction.

La citation - quoique concise - est essentiellement une tautologie. Il n'y a rien à réfuter et aucune évolution du matériel possible ne peut le rendre plus vrai. Il ne s'agit pas de matériel, mais de définition d'un algorithme déterministe. Il observe simplement que le déterminisme et le hasard sont incompatibles. Pour tout algorithme déterministe, tout son comportement est prédit par ses conditions de départ. Si vous pensez avoir trouvé une exception, vous ne comprenez pas ce que signifie être déterministe.

Il est vrai qu'un processus s'exécutant sur un ordinateur partagé avec une série complexe de caches et qui reçoit diverses entrées réseau et matérielles a accès à bien plus d'entropie qu'un processus s'exécutant sur du matériel simple, isolé et dédié. Mais si ce processus accède à cette entropie, il n'est plus déterministe et donc la citation ne s'applique pas.

Quiconque tente de générer des nombres aléatoires par des moyens déterministes vit, bien sûr, dans un état de péché.

Lorsque vous interprétez «vivre dans un état de péché» comme «faire un non-sens», c'est tout à fait vrai.

Ce que vous avez fait, c'est d'utiliser une méthode plutôt lente System.nanoTime()pour générer un caractère aléatoire plutôt faible. Vous en avez mesuré

... taux d'entropie de ~ 5,3 bits / octet ...

mais ce n'est que la limite supérieure. Tout ce que vous pouvez obtenir est une limite supérieure. L'entropie réelle peut être inférieure de plusieurs ordres de grandeur.

Essayez plutôt de remplir le tableau à l'aide d'un hachage cryptographique comme MD5. Calculez une séquence comme md5(0), md5(1), ...(à partir de chaque valeur prise un ou plusieurs octets, cela n'a pas d'importance). Vous n'obtiendrez aucune compression (oui, MD5 est cassé, mais toujours assez bon pour produire des données incompressibles).

Nous pouvons dire qu'il n'y a pas du tout d'entropie, mais vous mesureriez 8 bits / octet.

Lorsque vous avez vraiment besoin de quelque chose de aléatoire, vous devez non seulement utiliser une source HW, mais vous devez également connaître une limite inférieure sûre sur la quantité d'entropie qu'elle produit réellement. Bien qu'il y ait très probablement un peu de hasard nanoTime(), je ne suis au courant d'aucune borne inférieure non triviale.

Lorsque vous avez besoin d'aléatoire pour la cryptographie, vous devez vraiment recourir à quelque chose fourni par votre système d'exploitation, votre langue ou une bonne bibliothèque. Ces fournisseurs collectent l'entropie à partir de sources multiples et / ou de matériel dédié et un certain nombre de travaux ont été consacrés à ces estimations d'entropie.

Notez que vous n'avez généralement besoin d'aucune entropie. Un bon PRNG (déterministe) initialisé avec quelques octets aléatoires est utilisable pour la cryptographie, et donc aussi pour tout le reste.

Je pensais que je ferais sonner la signification de "aléatoire". La plupart des réponses parlent ici de la sortie de processus aléatoires , par rapport à la sortie de processus déterministes. C'est une très bonne signification de "aléatoire", mais ce n'est pas le seul.

Un problème avec la sortie des processus aléatoires est qu'ils sont difficiles à distinguer des sorties des processus déterministes: ils ne contiennent pas un "enregistrement" de la façon dont leur source était aléatoire. Un exemple extrême de cela est une célèbre bande dessinée XKCD où un générateur de nombres aléatoires revient toujours 4, avec un commentaire de code affirmant qu'il est aléatoire car il provient d'un jet de dé.

Une approche alternative pour définir le "caractère aléatoire", appelée complexité de Kolmogorov , est basée sur les données elles-mêmes, quelle que soit la façon dont elles ont été générées. La complexité de Kolmogorov de certaines données (par exemple une séquence de nombres) est la longueur du programme informatique le plus court qui produit ces données: les données sont "plus aléatoires" si elles ont une complexité de Kolmogorov plus élevée.

Votre utilisation d'algorithmes de compression comme PNG et la comparaison de la longueur avant et après la compression sont similaires à l'idée de complexité de Kolmogorov. Cependant, la complexité de Kolmogorov permet aux données d'être encodées en tant que programme dans n'importe quel langage de programmation complet de Turing, plutôt que dans un format limité comme PNG; "décompresser" ces encodages (programmes) se fait en les exécutant, ce qui peut prendre un temps et une mémoire arbitraires (par exemple plus que ce qui est disponible dans notre univers chétif).

Le théorème de Rice nous dit que nous ne pouvons pas, en général, faire de distinction entre les programmes qui bouclent pour toujours et les programmes qui produisent nos données. Par conséquent, il est très difficile de trouver la complexité de Kolmogorov de certaines données: si nous écrivons un programme qui génère ces données, il peut en fait y avoir un programme plus court (c'est-à-dire une complexité plus faible), mais nous ne l'avons pas repéré parce que nous ne pouvions pas le distinguer d'une boucle infinie. La complexité de Kolmogorov est donc non calculable, bien que si nous connaissions les nombres Busy-Beaver, nous pourrions le calculer en utilisant ceux-ci pour limiter la quantité de temps que nous vérifions chaque programme.

Dans le cas de vos données d'exemple, pour trouver sa complexité de Kolmogorov (c'est-à-dire "aléa intrinsèque"), nous aurions besoin de trouver le programme déterministe le plus court qui génère cette même séquence d'octets et de prendre sa longueur.

Nous pouvons maintenant répondre à votre question du point de vue de la complexité de Kolmogorov, et nous trouvons que la citation est correcte: nous ne pouvons pas générer de nombres aléatoires (complexité élevée de Kolmogorov) par des moyens déterministes.

Pourquoi pas? Imaginons que nous écrivions un petit programme informatique et que nous l'utilisions pour générer une séquence de nombres aléatoires. L'une des situations suivantes doit s'appliquer:

• Nous générons une grande quantité de sortie. Cependant, puisque nous savons que cette sortie est générée par un petit programme, la sortie (par définition) a une faible complexité de Kolmogorov, et donc elle n'est pas "aléatoire" dans ce sens.
• Nous générons si peu de nombres que les écrire tous prendrait à peu près les mêmes, voire moins, bits que l'écriture de notre programme de génération court. Dans ce cas, les nombres sont relativement incompressibles, ce qui indique qu'ils sont assez aléatoires au sens de Kolmogorov. Cependant, comme la quantité de sortie est comparable à ce que nous avons mis (le code source du programme), il est juste de dire que le programme n'a pas "généré" le caractère aléatoire, nous l'avons fait en choisissant ce programme. Après tout, dans ce cas, notre programme de génération aurait tout aussi bien pu être une liste de ces nombres exacts (par exemple print([...])).

Dans les deux cas, nous ne «générons» pas plus de hasard que nous n'en mettons (le «hasard» du code source de notre programme de génération). Nous pourrions essayer de contourner cela en utilisant un programme de génération plus long, pour éviter que la sortie n'ait un générateur court, mais il n'y a que deux façons de le faire:

• "Gonfler" systématiquement le code d'une manière ou d'une autre. Cependant, la complexité de Kolmogorov ne se soucie pas du programme particulier que nous avons utilisé pour générer les données: elle ne se soucie que du programme de génération le plus petit. Le gonflement systématique n'ajoute pas la complexité de Kolmogorov, car de tels modèles dans le code peuvent eux-mêmes être générés avec une très petite quantité de code. Par exemple, si nous prenons run(shortGenerator)et ajoutons une charge entière de ballonnement systématique pour obtenir run(bloatedGenerator), un générateur court existe toujours de la forme run(addBloat(shortGenerator)).
• Ajoutez un gonflement non systématique , c'est -à- dire sans aucun motif, de sorte qu'une addBloatfonction devrait finir par être aussi gonflée que le code lui-même. Cependant, être si dépourvu de motifs est exactement ce qui fait quelque chose de aléatoire (complexité élevée de Kolmogorov). Ballonnements D' où le programme de génération de cette manière n'augmenter le caractère aléatoire (complexité de Kolmogorov) de la production, mais elle aussi augmente la quantité de caractère aléatoire (complexité de Kolmogorov) que nous devons fournir sous la forme de code source. C'est donc toujours nous qui assurons le "hasard" et non le programme. Dans l'exemple ci-dessus d'écriture juste , l'ajout de ballonnements non systématiques équivaut à simplement écrire plus de nombres "aléatoires" dans cette liste codée en dur.print([...])

La compression n'est pas un test précis de l'aléatoire, ni regarder une image et dire "ça a l'air aléatoire".

L'aléatoire est testé par des méthodes empiriques . Il existe en fait des suites de logiciels / algorithmes spécialement conçus pour tester l'aléatoire, par exemple TestU01 et les tests Diehard .

De plus, votre image est en fait une chaîne de nombres 1D mappée sur un espace, et n'est donc pas une bonne représentation de certains motifs qui peuvent apparaître.

Si vous examiniez votre image pixel par pixel, vous trouveriez très probablement de nombreux modèles courts de valeur croissante avant une chute soudaine. Si vous deviez créer un graphique avec la valeur x étant le numéro d'échantillon et la valeur y étant la valeur obtenue à partir de la fonction `` aléatoire '', vous trouveriez très probablement que vos données ressemblent en fait à une onde en dents de scie:

C'est le modèle créé par les valeurs qui augmentent sous l'arithmétique modulaire (dont votre calcul est un exemple: le temps augmente à un taux presque constant et & 0xFFagit comme mod 256).

Vous confondez le concept de nombres aléatoires avec des «nombres qui semblent être aléatoires».

Pour comprendre la citation de von Neumann, nous devons comprendre ce que signifie «générer des nombres aléatoires». La réponse de Warbo relie un excellent XKCD à cette fin:

Lorsque nous parlons de nombres aléatoires, nous ne parlons pas des valeurs elles-mêmes. De toute évidence, un 4 n'est pas plus aléatoire qu'un 3. Nous parlons de la capacité d'un tiers à prédire cette valeur mieux que le hasard. Un nombre aléatoire est un nombre qui n'est pas prévisible. Parfois, nous ajoutons des conditions à cela. Un générateur de nombres pseudo-aléatoires cryptographiquement sécurisé (CSPRNG) génère des nombres qui ne peuvent pas être prédits mieux que le hasard si un attaquant ne connaît pas la graine / clé, mais si nous parlons de nombres vraiment aléatoires (pas pseudo-aléatoires), son généralement défini comme étant un nombre qui n'est pas prévisible, même avec une connaissance complète du système, y compris les clés.

Maintenant, votre exemple, comme beaucoup l'ont souligné, n'est pas déterministe. Le programme ne spécifie pas de quelle valeur sort System.nanoTime(). Ainsi, il n'est pas dans la même classe que l'utilisation d'un CSPRNG pour générer des nombres pseudo aléatoires. Le premier peut être non déterministe tandis que le second est déterministe si la valeur de la clé est déterministe. Le premier contient des opérations qui ne sont pas définies pour avoir des valeurs déterministes.

Cependant, vous remarquerez que j'ai dit que ce n'était peut- être pas déterministe. N'oubliez pas que ce System.nanoTime()n'est pas conçu pour fournir des valeurs à cet effet. Il peut ou non être suffisamment non déterministe. Une application peut ajuster l'horloge système de telle sorte que les appels à System.nanoTime()tous se produisent sur des multiples de 256 nanosecondes (ou près). Ou vous travaillez peut-être en Javascript, où les récents exploits de Spectre ont conduit les principaux navigateurs à réduire intentionnellement la résolution de leurs minuteries. Dans ces cas, vos «nombres aléatoires» peuvent devenir hautement prévisibles dans des environnements que vous n'aviez pas planifiés.

• Donc, générer des nombres aléatoires avec des processus déterministes ... le péché.
• Générer des nombres aléatoires avec du matériel aléatoire dédié ... pas pécher.
• Générer des nombres aléatoires avec des aspects non déterministes des ordinateurs ... peut-être le péché.

Tout dépend de ce que vous envisagez. Si vous cryptez vos lettres d'amour à Bob l'éponge afin que votre sœur ne puisse pas les lire, les exigences imposées à vos soi-disant nombres aléatoires sont assez faibles. System.nanoTime()utilisé comme vous l'avez fait est probablement assez bon. Si vous protégez des secrets nucléaires contre un État étranger avancé qui les recherche activement, vous voudrez peut-être envisager d'utiliser du matériel conçu pour relever le défi.

Je ne pense pas que vous ayez compris la demande. Le fait est que s'il existe une procédure déterministe pour générer une série de nombres «aléatoires» (ou quoi que ce soit, vraiment), alors trouver le modèle est simplement la tâche de trouver cette procédure!

Par conséquent, il existe toujours une méthode déterministe pour prédire le prochain entier. C'est précisément ce à quoi nous ne nous attendons pas si nous supposons le hasard!

Toute déterminisme suffisamment complexe ne se distingue pas de la stochasticité.

--À partir de la page utilisateur de Wrzlprmft

Par conséquent, même si quelque chose semble aléatoire, pourquoi diable le modéliserions-nous comme «aléatoire» si nous avons une procédure déterministe pour le générer?

C'est, je pense, le problème clé. Vous venez de montrer une certaine forme d' indiscernabilité du PRNG et du «vrai hasard».

Cependant, le fait que ces concepts soient donc égaux ne suit pas. En particulier, le hasard est un concept mathématique et théorique . Nous avons déjà montré ci-dessus qu'en théorie, considérer le PRNG comme un «vrai hasard» conduit à une contradiction. Par conséquent, ils ne peuvent pas être égaux.

Je pense que d'autres l'ont déjà souligné, mais ce n'est pas ce qui souligne, alors permettez-moi également d'ajouter à la discussion.

Comme d'autres l'ont déjà souligné, il y a le problème de la mesure de l'entropie. Les algorithmes de compression peuvent vous dire quelque chose, mais ils sont indépendants de la source. Puisque vous en savez plus sur la façon dont les données ont été générées, vous pourriez probablement construire un algorithme bien meilleur pour les compresser, ce qui signifie que la véritable entropie est beaucoup plus faible.

De plus, vous vous méprenez quelque peu sur le sens des phrases "sur ordinateur" et "déterministe". Vous certainement pouvez effectuer une opération non déterministe sur l'ordinateur.

De plus, en fait, vous venez de le faire , mais ce n'est pas si évident à première vue.

Un typique algorithme déterministe pour une génération de nombres aléatoires est ie. PRNG comme générateur congruentiel linéaire. Ils sont avec état. L'état intérieur signifie moins d'entropie puisque l'état suivant est déterminé par le précédent. Je ne m'étendrai pas là-dessus, c'est probablement évident pour vous. Un point important est que l'algorithme entièrement déterministe ne dépend que de l'état précédent, quel qu'il soit.

Regardez maintenant votre algorithme. Sur quoi est-il basé? Quel état avez-vous? Est-ce déterministe?

  file.writeByte((byte) (System.nanoTime() & 0xff));

Ignorons file.write et tous les problèmes de vidage des tampons, en attente d'E / S (avez-vous essayé d'ajouter du bruit sur les câbles du disque dur pendant un moment? Non? Hé vous pourriez le faire. Hé, ce n'est pas déterministe alors! :)), et concentrons-nous sur la source, c'est plus important.

Le temps est une sorte d'état. Cela varie, mais la plupart sont les mêmes. C'est pourquoi vous avez essayé de le contourner et avez pris & 0xFF pour tomber plupart de l'état. Mais vous n'avez pas tout laissé tomber, certains états de la lecture précédente peuvent fuir vers le suivant, donc ce n'est certainement pas totalement non déterministe *)

Mais cela ne nous intéresse pas. Pour «prouver» que la citation est fausse:

Quiconque tente de générer des nombres aléatoires par des moyens déterministes vit, bien sûr, dans un état de péché.

Vous devez le prouver par un moyen déterministe.
Ce qui nous intéresse, c'est: votre algo est-il certainement pleinement déterministe ?

..et il est évident que ce n'est pas le cas.

  System.nanoTime() & 0xff

C'est une mesure du temps. Temps et mesure . La partie de mesure peut la rendre déterministe si la valeur est mise en cache. Je suppose que ce n'est pas le cas, sinon cette fonction n'aurait aucun sens. Ensuite, s'il est lu à la volée depuis la source, nous avons une valeur temporelle. Puisque ( je suppose encore une fois ) que vous n'avez pas exécuté cela sur un matériel dédié à une seule tâche, vous pouvez parfois avoir un changement de contexte. Même si vous disposiez d'un matériel dédié à une seule tâche, la mesure du temps peut toujours ne pas être déterministe, en raison de dérives de température / humidité dans la source de temps, les heures de synchronisation du bus, etc.

Je suis tout à fait d'accord pour exagérer ici. Les dérives ne seront pas si importantes pour avoir beaucoup d'impact (bien que pour de vrai nanotimeelles pourraient l'être). Plus important,nanotime est censé être rapide. Il ne lit pas à partir d'une source en temps réel. Il est basé sur le nombre d'instructions / cycles internes du processeur. C'est en fait déterministe, si vous vous assurez qu'aucun changement de contexte.

Mon point est qu'il peut être très difficile d'exécuter un algorithme vraiment 100% déterministe si vous le basez sur le temps, et vous n'avez pas le droit de réfuter cette citation à moins d'avoir des moyens entièrement déterministes.

*) Fait intéressant, vous pourriez probablement augmenter le caractère aléatoire réel si vous optez pour le hardcore. Faites & 0x01, bit par bit, et attendez les threads un certain temps avant de lire chaque bit. La génération de données de cette façon serait ridiculement longue, mais je dirais en fait qu'elle pourrait être considérée comme presque vraiment aléatoire, l'IIF que vous exécutez sur non-RTOS et également l'IFF à chaque `` temps notable '' sont suffisamment élevés pour garantir que le sous-jacent Le système d'exploitation s'est mis en veille ou a changé de contexte pour une autre tâche.

Je pense que la réponse dont vous avez besoin commence par ce commentaire que vous avez vous-même fait en réponse à une autre réponse:

Le modèle est le résultat de l'interaction de Java, de la JVM, du système d'exploitation, des caches CPU +, du disque dur, de la musique Trance que je diffusais en continu, qui consomme des cycles CPU / RAM et tout le reste. Le modèle provient simplement d'une ligne de code Java à l'intérieur d'une boucle for / next. Une partie importante de l'entropie provient des circuits matériels sous-jacents.

Vous le savez déjà, je pense: vous n'avez pas utilisé de moyens déterministes pour créer le motif.

Vous avez utilisé un ordinateur, dont une partie non négligeable est déterministe, mais l'entropie provenait de sources externes non déterministes (ou du moins non déterministes à toutes fins pratiques pour le moment): vous ou le monde extérieur interagissant avec l'ordinateur (et dans une moindre mesure, toute imperfection physique du matériel informatique qui pourrait affecter le timing des choses).

Soit dit en passant, c'est une grande partie de la façon dont les systèmes d'exploitation modernes sement leurs générateurs de nombres aléatoires qui sont disponibles pour les programmes: en exploitant l'entropie dans les interactions avec son matériel et l'utilisateur que nous espérons ne sont pas prévisibles pour un attaquant.

Soit dit en passant, l'entropie du monde extérieur est en fait un problème qui doit être traité à ce jour dans une cryptographie autrement bien codée: les ordinateurs qui ont un comportement prévisibleau démarrage et pendant leur exécution, tels que ceux avec un stockage en lecture seule ou qui démarrent à partir du réseau et qui ont un environnement réseau prévisible (soit non attaché à un réseau ou la charge de travail sur le réseau est suffisamment faible pour que tout soit livré dans un temps fiable), et qui exécutent le même ensemble limité de logiciels avec un comportement à peu près cohérent, pourraient surestimer considérablement l'entropie qu'ils obtiennent de ces composants supposés imprévisibles, et finir par générer des nombres beaucoup plus prévisibles que vous obtiendriez sur un poste de travail typique qui fait toutes sortes d'autres choses pour vous (streaming de musique, synchronisation avec dropbox, peu importe) en arrière-plan.

Je pense que la plupart des réponses se concentrent sur la question de savoir si la vérification des huit derniers bits de mesure du temps en nanosecondes prises en boucle est un bon moyen de récolter cette entropie. C'est une question très importante à laquelle répondre correctement avant d'utiliser la méthode dans votre exemple comme schéma de génération de nombres aléatoires dans la pratique , mais c'est une question distincte de ce que je pense que vous posez.

Pour compléter les réponses précédentes, voici un moyen simple de réfléchir à cette question.

Tout dépend de la différence entre aléatoire et déterministe . Nous allons venir à Von Neumann et ce qu'il disait, après.

Nombres aléatoires

Un véritable générateur de nombres aléatoires n'aurait aucun motif, même pas caché en arrière-plan, que nous pourrions utiliser pour prédire le nombre suivant étant donné la séquence jusqu'à présent. Dans un monde idéal, vous pourriez savoir tout ce qu'il y a à savoir dans l'univers physique et sur le système, nanoseconde par nanoseconde, et il serait toujours inutile d'essayer de prédire le prochain nombre produit.

C'est un cas idéal - en termes pratiques, nous y arrivons en mélangeant de nombreuses sources qui ne sont "pas de mauvaises approximations" au hasard, ou qui sont vraiment aléatoires, ou qui mélangent suffisamment les choses mathématiquement pour que vous puissiez prouver mathématiquement qu'elles se rapprochent de l'imprévisible et manque de parti pris pour des nombres ou des schémas spécifiques.

• Les «bonnes» sources sont des choses similaires à l'attente d'un processus de désintégration radioactive ou d'un autre processus quantique intrinsèquement imprévisible. Sortie d'un semi-conducteur sensible à la chaleur. Bruit aléatoire dans une diode ou un autre matériau électrique. Compter les photons du soleil.

• Mélangé à cela, nous pouvons également ajouter certains que nous considérons comme "pas mal" qui aident car ils n'ont aucune connexion à ceux-ci: En attente du prochain clic de souris ou du paquet réseau. Dernier microtime à l'écriture du fichier suivant. Sortie d'une fonction de générateur de nombres pseudo-aléatoires "connue mais mathématiquement assez aléatoire". Entropie précédente des utilisations précédentes de nombres aléatoires.

Le but ici est d'obtenir un nombre qui ne peut toujours pas être prédit , quoi que ce soit dans l'univers que vous connaissez , et qui est statistiquement aussi probable que cela, sans schéma, biais ou prévisibilité mathématiquement détectable, et sans corrélation avec un événement qui pourrait être surveillé et utilisé pour la prédiction. (Ou s'il est corrélé à un événement, cela se fait d'une manière qui rend la connexion incroyablement ténue, comme "un chiffre en nanosecondes uniquement au moment du dernier clic de souris").

Nombres déterministes

Les mathématiciens peuvent prouver des choses sur les formules et les fonctions. Il est donc possible de prouver qu'une fonction, lorsqu'elle est appelée à plusieurs reprises, ne donne aucun parti pris ou préférence à aucun modèle, autre que le modèle simple "ce sont les sorties de cette fonction si elle est appelée à plusieurs reprises".

Ainsi, par exemple, si vous choisissez un nombre, par exemple entre 1 et 10 millions, l'écrivez en binaire et le "hachez" à plusieurs reprises, vous obtiendrez une séquence de chiffres assez aléatoire. C'est presque aléatoire - mais ce n'est pas du tout aléatoire. Vous pouvez prédire, étant donné l'algorithme et n'importe quel état, quel sera le prochain nombre.

Nous l'appelons "pseudo-aléatoire" car il semble et semble être principalement aléatoire, même s'il ne l'est pas.

Voici un bon exemple. Pensez à cette séquence de "nombres aléatoires" à 3 chiffres: 983, 367, 336, 244, 065, 664, 308, 602, 139, 494, 639, 522, 473, 719, 070, 217. Disons que je vous dis Je peux générer un million de numéros de la même manière. Vous pouvez alors passer à un statisticien qui confirmera (disons) qu'ils sont répartis également ou quoi que ce soit. Il n'y a pas de schéma prévisible évidentb. Ils ont l'air assez aléatoires, non? Mais maintenant je vous dis qu'ils sont en fait

le 500e + chiffre de Pi, groupé en 3s.

Soudain, cependant aléatoire

chiffres de Pi

peut être, vous pouvez immédiatement prédire que les 2 prochains numéros seront 986 et 094.

Pour être clair, je ne sais pas exactement à quel point le

chiffres de Pi

sont. Il aura été étudié et la réponse bien connue. Mais le fait est le suivant: en principe, la même conclusion est vraie pour toute source produite à la suite d'un processus déterministe .

Entre

Entre les deux, il y a toute une gamme de «choses qui semblent aléatoires et sont souvent aléatoires dans une certaine mesure». Plus on peut mélanger de façon aléatoire et presque aléatoire, moins la sortie est sujette à la possibilité de détecter n'importe quel motif ou de prédire n'importe quelle sortie, mathématiquement.

Retour à von Neumann et votre question

Comme vous pouvez le voir, les sorties déterministes peuvent sembler aléatoires, et peuvent même, statistiquement, être distribuées de manière aléatoire. Ils pourraient même utiliser des données «secrètes» ou à évolution rapide que nous n'avons aucun espoir réaliste de connaître. Mais tant qu'il est déterministe, les chiffres ne peuvent toujours pas vraiment être aléatoires . Ils ne peuvent être "assez proches du hasard que nous sommes heureux d'oublier la différence".

C'est le sens de la citation que vous avez donnée. Un processus déterministe ne peut tout simplement pas donner des nombres aléatoires. Il ne peut donner que des nombres qui semblent être, et se comportent tout à fait comme des nombres aléatoires.

Nous pouvons maintenant reformuler votre question comme ceci: "La sortie de mon ordinateur (ou de tout autre ordinateur moderne) peut ressembler et se comporter de manière totalement aléatoire, cela signifie-t-il que la citation de von Neumann est désormais dépassée et incorrecte?"

Le problème est toujours le suivant: même si la sortie de votre ordinateur peut sembler et se comporter de manière aléatoire, elle peut ne pas être vraiment aléatoire . Si elle est uniquement calculée de manière déterministe, cela signifie qu'il n'y a rien qui ne soit pas un effet de cause préductible à propos de l'obtention du nombre suivant (c'est ce que signifie "déterministe" dans ce sens). Nous commençons avec certaines données existantes (connues), nous appliquons un processus connu (complexe ou désordonné ou autre), et nous obtenons ce qui semble être un nouveau "nombre aléatoire". Mais ce n'est pas aléatoire, car le processus était déterministe.

Si vous dites que votre méthode comprendra un véritable générateur aléatoire matériel, pour corriger cela (comme un nombre aléatoire généré par la désintégration radioactive ou le bruit dans un semi-conducteur), alors votre réponse pourrait maintenant être aléatoire - mais votre méthode par définition n'est plus déterministe , précisément parce que vous ne pouvez plus prédire les sorties (ou effets) compte tenu des entrées / données initiales (causes) .

Von Neumann gagne dans les deux sens, presque par définition!