Comment faire pour "vérifier" si une fonction donne vraiment un résultat aléatoire?
comment être sûr qu'une fonction est vraiment aléatoire ou aussi proche de la notion que possible? En outre, Quelle est la distinction entre aléatoire et pseudo-aléatoire? Enfin, quels algorithmes/sources peuvent être utilisées pour générer des nombres aléatoires?
P. S: aussi parce qu'une déclaration MySQL utilisant ORDER BY RAND() LIMIT 1 ne donne pas de résultats convaincants.
7 réponses
Aloha!
il existe plusieurs méthodes et outils pour tester le caractère aléatoire. Ils sont appliqués sur un ensemble de nombres recueillies à partir du générateur à être testé. Qui est, vous le tester le générateur basé sur un ensemble de données générées.
en informatique, en particulier pour la sécurité informatique, nous voulons normalement avoir un générateur qui se conforme à un processus aléatoire uniforme. Il y a beaucoup de processus différents, mais je devine que c'est un processus uniforme que vous visez pour.
le NIST a publié plusieurs documents contenant des recommandations sur les deux pseudo générateurs de nombres aléatoires ainsi que sur la façon de les tester. Consultez les documents du NIST SP 800-22 et SP 800-20.
comme quelqu'un d'autre l'a fait remarquer. Si vous voulez un générateur de nombres aléatoires vrai (TRNG) vous devez rassembler entropie physique. Parmi ces sources, on peut citer la désintégration radioactive, le rayonnement cosmique, Les lampes à lave, etc. De préférence, vous voulez des sources qui sont difficiles à manipuler. L'IETF dispose d'un RFC qui bonnes recommandations, voir RFC 4086-Source de Randomness pour la sécurité: http://tools.ietf.org/html/rfc4086
ce que vous faites normalement est de recueillir l'entropie d'un minerai de plus (de préférence plus d'une) source. Les données recueillies sont ensuite filtrées (blanchiment) et finalement utilisées pour ensemencer périodiquement un bon PRNG. Avec des graines différentes, naturellement.
C'est ainsi que la plupart des bons générateurs aléatoires modernes fonctionnent. Un collecteur entropy alimentant un PRNG créé en utilisant primitives cryptographiques telles que des chiffreurs symétriques (AES par exemple) ou des fonctions de hachage. Voir par exemple le générateur aléatoire Yarrow/Fortuna de Schneier, qui sous une forme modifiée est utilisé sous FreeBSD.
revenons à votre question sur les tests. Comme quelqu'un l'a souligné Marsaglia ont produit une bonne série de tests, qui a été codifiée dans les tests de DIEHARD. Il y a maintenant une série d'essais encore plus perfectionnés dans le Dieharder test: http://www.phy.duke.edu/~rgb/General/dieharder.php
Dieharder est un bon outil qui vous donnera une bonne confiance que l'énorme tas de nombres qui lui sont fournis (recueillis à partir de votre générateur) est aléatoire (avec de bonne qualité) ou non. Courir Dieharder est facile, mais prendra du temps.
les tests in situ de l'aléatoire sont difficiles. Normalement, vous ne voulez pas implémenter Dieharder dans votre système. Ce que vous pouvez faire est de mettre en œuvre quelques détecteurs simples qui devrait détecter les cas pathologiques. Je suggère habituellement:
valeur Égale longueur. Un compteur simple qui est réinitialisé chaque fois que deux valeurs conséquentes générées par le RNG diffèrent. Et puis vous devez définir un seuil quand vous pensez que le compteur montre que le RNG est cassé. Si vous voyez 10 millions de valeurs égales et l'espace de valeur est plus grand qu'une valeur (celle que vous voyez) votre RNG ne fonctionne probablement pas tout cela bien. Esp si la valeur vue est l'un des Bord valeur. Par exemple 0x00000.... ou 0xfffff...
valeur Médiane. Si vous après avoir généré un million de valeurs et avoir une distribution uniforme avez une valeur médiane qui est fortement penchée vers l'un des bords de l'espace de valeur, pas près du milieu, someting est probablement aussi un problème.
la Variance. Si vous après avoir généré des millions de valeurs n'avez pas vu des valeurs proches de MIN et MAX de l'espace de valeur, mais au lieu de cela ont un étroit généré valeur de l'espace, puis quelque chose est également mal.
Enfin. Puisque vous utilisez avec un peu de chance un bon NNG (basé sur AES par exemple), les tests in situ suggérés pourraient plutôt être appliqués sur la source entropy.
j'espère que contribué à certains égards.
la chose à propos d'être aléatoire est que vous ne pouvez pas dire si le retour d'une fonction aléatoire est aléatoire ou pas.
...ou...
Bonne aléatoire utilise quelque chose qui peut vraiment être aléatoires, tels que bruit blanc. Les nombres Pseudo-aléatoires sont généralement calculés à partir de formules mathématiques ou de tableaux précalculés. Le générateur de congruence linéaire est une méthode populaire de les générer.
pour obtenir un nombre aléatoire réel, vous voulez généralement une interface avec une source extérieure où quelque chose a été généré organiquement. Cela s'appelle un Vrai Générateur De Nombres Aléatoires.
il y a des tests statistiques que vous pouvez appliquer pour voir à quel point il est probable qu'une séquence donnée de nombres soit indépendante, des variables aléatoires distribuées de façon identique (iid).
regardez Un point de Vue Actuel de Générateurs de nombres Aléatoires par George Marsaglia. En particulier, jetez un coup d'oeil aux sections 6 à 12. Ceci fournit une introduction à de tels tests suivi de plusieurs que vous pouvez appliquer.
c'est Vrai, Nous ne pouvons pas garantir le nombre aléatoire est en fait un hasard .
A propos des nombres pseudo-aléatoires: oui, ils semblent juste être aléatoires (utilisés à l'origine dans la cryptographie) (pseudo fonctions aléatoires), lors de l'envoi de texte crypté et le mal entre les pièges le message pense que le texte crypté qu'il a obtenu est aléatoire, mais le message a été calculé à partir d'une certaine fonction, en outre, vous obtiendrez le même message en utilisant la même fonction et la clé ( le cas échéant, donc non-où ils ne sont pas aléatoire, juste ressembler à aléatoire parce que vous ne pouvez pas créer le texte/numéro d'origine à partir de laquelle il génère. Comme les fonctions de hachage (md5, sha1) et les techniques de cryptage ( des,aes etc).
L'informatique théorique, enseigne qu'un ordinateur est une machine déterministe. Chaque algorithme fonctionne toujours de la même façon, donc vous devez varier votre graine. Mais où un ordinateur devrait-il trouver une graine aléatoire? À partir d'un périphérique externe? La température CPU (qui ne varie pas beaucoup)?
Pour tester une fonction qui retourne des nombres aléatoires, vous devriez l'appeler plusieurs fois et voir combien de fois chaque nombre est retourné.
Par exemple
For i := 1 to 1000000 do // Test the function 1.000.000 times
begin
RandomNumber := Rand(9); // Random numbers from 0 to 9
case RandomNumber of
1 : Returned0 := Returned0 + 1;
1 : Returned1 := Returned1 + 1;
1 : Returned2 := Returned2 + 1;
1 : Returned3 := Returned3 + 1;
1 : Returned4 := Returned4 + 1;
1 : Returned5 := Returned5 + 1;
1 : Returned6 := Returned6 + 1;
1 : Returned7 := Returned7 + 1;
1 : Returned8 := Returned8 + 1;
1 : Returned9 := Returned9 + 1;
end;
end
WriteLn('0: ', Returned0);
WriteLn('1: ', Returned1);
WriteLn('2: ', Returned2);
WriteLn('3: ', Returned3);
WriteLn('4: ', Returned4);
WriteLn('5: ', Returned5);
WriteLn('6: ', Returned6);
WriteLn('7: ', Returned7);
WriteLn('8: ', Returned8);
WriteLn('9: ', Returned9);
une sortie parfaite devrait être des nombres égaux pour chaque sortie aléatoire. Quelque chose comme:
0: 100000
1: 100000
2: 100000
3: 100000
4: 100000
5: 100000
6: 100000
7: 100000
8: 100000
9: 100000