Journal Sortie de la bibliothèque Hasard version 0.2

Posté par (page perso) .
Tags : aucun
0
31
mai
2008
La faille de sécurité OpenSSL+Debian m'a motivé à lancer un projet que j'avais en tête depuis quelques temps : écrire une bibliothèque haut niveau pour gérer les nombres pseudo-aléatoires.
http://haypo.hachoir.org/trac/wiki/hasard

Ma motivation est que l'API C, srand() et rand(), est difficile à utiliser et peu de gens l'utilisent correctement. L'idée est donc de créer des fonctions qui empêchent les erreurs courantes : utilisation d'une faille entropie pour initialiser le générateur (typiquement time(NULL), voir getpid() et getppid()), utilisation de rand()%nombre pour générer un nombre dans l'intervalle [0; nombre-1].

J'ai donc écrit des fonctions pour générer des booleans, des entiers dans un intervalle, des nombres flottants et des octets aléatoires. La bibliothèque hasard supporte de nombreux générateurs (Mersenne Twister, ISAAC, Park-Miller, RANDU, ...) pour générer des nombres, et divers générateurs pour initialiser la graine (/dev/urandom et /dev/random pour l'instant). Par défaut c'est Mersenne Twister qui est utilisé avec /dev/urandom.

Pour faciliter l'intégration dans des biblitohèques et projets existants, la licence choisie est la licence BSD. La bibliothèque est écrite en C et un binding Python est disponible (tests/hasard.py). Le code est encore en développement et mériterait d'être relu. J'ai écrit divers tests pour mesurer l'entropie, tester les algorithmes, lancer le programme ENT (calcule divers statistiques sur les nombres), etc.

Pour la suite, il faudrait améliorer la portabilité (pour l'instant, hasard vise surtout Linux) en implémentant d'autres générateurs matériels : code pour Windows, EGD, instruction Intel "XSTORE RNG", etc. Des tests doivent être fait sur processeur 64 bits et/ou big endian. Voir le fichier README pour les autres idées de développement.
  • # À quoi ça sert…

    Posté par . Évalué à 10.

    …que d’autres se décarcassent ?

    Il y a déjà http://www.gnu.org/software/gsl/ , qui a des bindings ruby, ocaml, s-lang, octave, python, etc., qui est bien testée, qui possède tout un tas de générateurs, qui permet tout un tas de distributions, qui est portable…

    Il y a aussi http://www.boost.org/doc/libs/release/libs/random pour le C++, mêmes avantages que GSL.

    Et il y en a d’autres, comme http://sprng.cs.fsu.edu/ ou bien plusieurs petites bibliothèques qui offrent des générateurs aléatoires (cf. apt-cache search random lib ou équivalent).
    • [^] # Re: À quoi ça sert…

      Posté par . Évalué à 3.

      Ça peut être très intéressant l'infrastructure de tests, on peut imaginer des programmes qui retrouveraient l'état interne du générateur à partir d'aléas si on sait lequel est utilisé (et s'il n'y a pas de retraitement par une fonction de hachage).

      En revanche, il est vrai que pour un usage cryptographique (à peu près le seul où il y a vraiment besoin d'aléas non prévisible) c'est délicat de tout réimplémenter de façon sûre et rapide.
    • [^] # Re: À quoi ça sert…

      Posté par (page perso) . Évalué à 8.

      Pour répondre franchement, je ne connaissais pas GSL, ni Boost Random, ni le 3e lien. D'ailleurs, il semble qu'OpenSSL, libgcrypt et Wormux ne les connaissent pas non plus :-) C'est justement le constat auquel je suis arrivé : chacun recode sa bibliothèque dans son coin. Selon moi, la génération de nombres pseudo-aléatoires est un problème suffisamment complexe pour qu'il mérite sa propre bibliothèque.

      Je pense donc récupérer les meilleurs morceaux d'OpenSSL, libgcrypt, et autres (ex: GSL) pour faire une bibliothèque dédiée. Puis en suite, propose à ces projets de réutiliser mon code. Le but serait de concentrer les efforts pour obtenir un code de meilleur qualité que du code que chacun écrit dans son coin.

      Maintenant, peut-être qu'effectivement il existe déjà une bibliothèque comme celle que j'essaye d'écrire, mais je ne suis pas au courant. Je vais voir les URLs que tu as postée, merci :-)
      • [^] # Re: À quoi ça sert…

        Posté par (page perso) . Évalué à 10.

        J'ai regardé GSL vite fait. Cette bibliothèque ne s'occupe pas d'initialiser la graine du générateur (elle initialise à zéro), or c'est le point le plus critique ! J'ai regardé l'implémentation de Mersenne Twister et on peut seulement injecter 32 bits d'entropie, alors que ma bibliothèque utilise 4*32 bits d'entropie (et encore, je me dis que ça fait peu, faut voir). De plus, il n'y pas de fonction pour générer un boolean par exemple.

        Côté positif, GSL a de nombreuses fonctions pour lire et restaurer l'état d'un générateur. C'est très intéressant. J'avais commencé à coder ça dans libhasard, mais je n'ai pas réussi à me décider sur la manière de le faire. GSL a également plus d'algorithmes : ranlux, ranlxs, cmrg, mrg, taus, gfsr4, bsd, libc5, glibc2, 3 variantes de Mersenne Twister, ... Maintenant, je pense que je pourrai toujours rajouter des algorithmes après, mais je veux surtout une base solide ;-)
      • [^] # Re: À quoi ça sert…

        Posté par . Évalué à 1.

        "Pour répondre franchement, je ne connaissais pas GSL"

        Cher Victor c'est une mauvaise réponse! Si tu avais posé la question, je t'aurais dit que la GSL existait et que le CERN la vérifié :

        http://lcgapp.cern.ch/project/cls/work-packages/mathlibs/ind(...)
        http://seal.cern.ch/documents/mathlib/thesis_marte.pdf

        cf. "Tests and validation of random number generators (see technical student report)"

        Si OpenSSL ne la connaît pas, c'est normal c'est pas le même champ d'application (scope). La cryptologie utilise un PRNG uniforme. La GSL from Los Alamos (disneyland pour les militants de Greenpeace) est fait pour les scientifiques et permet de générer des distributions.

        Voilà de quoi potasser sur le sujet.

        Je suppose que ENT est un outil dédié à la prédiction du cours des actions d'Autodesk. Au passage l'histoire de la naissance du géant fait en LaTeX est une curiosité mémorable! Sacré Bacula! La pompe à fric procure la sécurité des données ...

        p.s. : The etymology of the word "hazard" comes from French "hasard", from Old Spanish "azar", from Arabic "al-zahr" wich means the die. Example "hazardous area". Soit un nom pertinant pour un virus, make ...
        • [^] # Hasard != Hazard

          Posté par (page perso) . Évalué à 5.

          p.s. : The etymology of the word "hazard" comes from French "hasard", from Old Spanish "azar", from Arabic "al-zahr" wich means the die. Example "hazardous area". Soit un nom pertinant pour un virus, make ...

          Hasard (français, "Randomness" en anglais) != Hazard (anglais, "Risque" en français)
          http://www.cnrtl.fr/definition/Hasard
          http://fr.wikipedia.org/wiki/Hasard

          On n'est au 21e siècle, pas a 13è siècle, l'origine peut dater du 13è siècle, ça n'empêche pas que le mot a évolué depuis dans notre langue... Pour ne rien avoir à faire avec l'idée d'un virus.
          • [^] # Re: Hasard != Hazard

            Posté par . Évalué à 0.

            Ma phrase est à prendre au second degré. Je me suis donné la peine de télécharger, et de lire le README en anglais. Pour un anglophone "hasard" ça signifie un danger avec une faute d'orthographe. C'est du Marketing de base. Imagine qu'un jeune homme allemand dit à une française qui parle un peu sa langue "Du bist ein? salope" C'est mal baré ...
          • [^] # Re: Hasard != Hazard

            Posté par (page perso) . Évalué à 2.

            Effectivement, en anglais le mot « hazard » fait plutôt peur (ex: biohazard). Peut-être que le nom est mal choisi. Au début j'avais choisi « random », mais c'est comme qui dirait un peu trop courant :-) J'ai pensé mettre le logo « biohazard » sur la page du projet, mais je crains que la blague ne soit pas comprise et qu'au contraire ça porte encore plus à confusion :-) J'ai pris un mot français pour continuer ma série Hachoir, Fusil, etc. :-) Bah au pire, je peux changer le nom du projet, si ce n'est que ça...
        • [^] # Re: À quoi ça sert…

          Posté par (page perso) . Évalué à 3.

          Hum, je ne comprend pas ta prose. Est-ce de l'humour ou de la poésie ? En particulier :

          Je suppose que ENT est un outil dédié à la prédiction du cours des actions d'Autodesk.

          Euh, est-ce que signifie qu'ENT n'est pas fiable ? Si tu as d'autres propositions, je suis preneur. Je pense que je vais utiliser Diehard(er) et ses copains. Là j'ai pris ENT car c'est le premier auquel j'ai pensé et qu'il est simple à utiliser.

          Au passage l'histoire de la naissance du géant fait en LaTeX est une curiosité mémorable! Sacré Bacula! La pompe à fric procure la sécurité des données ...

          Rien compris. C'est qui/quoi le géant fait en LaTeX ?
      • [^] # Re: À quoi ça sert…

        Posté par . Évalué à 7.

        Je pense donc récupérer les meilleurs morceaux d'OpenSSL, libgcrypt, et autres (ex: GSL) pour faire une bibliothèque dédiée.

        Gare aux licences…

        Puis en suite, propose à ces projets de réutiliser mon code.

        < mauvais esprit >Ouais, je pompes le code puis je le rends… < / >

        Le but serait de concentrer les efforts pour obtenir un code de meilleur qualité que du code que chacun écrit dans son coin.

        Mon avis serait que participer à GSL (p.ex.) pour améliorer la partie Aléa serait un meilleur remède aux deux maux que sont la « mauvaise » qualité du code et le « chacun écrit dans son coin » (en fait, je ne vois pas en quoi le fait que ce soit toi qui écrive fasse que ce soit moins « dans son coin », et, même si c’est censé être repris plus tard, pourquoi les auteurs de GSL (toujours p.ex.) ne participeraient pas. D’autre part, à la base, je n’ai pas vraiment l’impression que GSL soit « écrit dans son coin » ou par des non-spécialistes.)
        Et, de là, de discuter avec GSL pour « sortir » (ou « désolidariser ») la partie Aléa (et, possiblement, de se rendre compte que ça n’a pas vraiment de sens parce que cette partie utilise d’autres parties de base de la GSL et, qu’au final, tout mettre ensemble n’est pas si gênant (ou pas)).

        En fait, j’ai l’impression que beaucoup refont leur petite fonction dans leur coin pour les raisons suivantes :
        — pourquoi chercher ailleurs ?
        — je n’ai pas besoin de grand-chose, une bidouille suffira ;
        — c’est un problème simple / connu / vieux, je suis capable de le faire ;
        — le syndrome « pas inventé ici, donc on n’a pas confiance » ;
        — le syndrome « ouh là la, mais c’est un canon pour écraser un moustique cette bibliothèque ».

        Et, toi-même, tu ne connais pas ce qui existe, donc tu ne t’en sers pas, donc tu as réinventé la roue comme les autres, ou tu veux le faire, et tu trouves que ce qui existe est trop gros…

        Ça vaudrait aussi pour Boost : pourquoi refont-ils ce que GSL fait ? Boost est aussi moins complet que GSL…
        En fait, je crois qu’ils diraient — et c’est peut-être un indice sur la difficulté de la faisabilité de la séparation de la partie aléa du reste de la GSL —, les générateurs sont liés aux types (int, float…) et, en plus, Boost fait du vrai C++ et veut intégrer tout ça à ses templates…

        Sinon, pour info, libgsl.so.0 fait moins de 2 Mio en x86_64 (idem pour le paquet -dev avec tous les .h et le .a). Ce qui n’est pas énorme pour tout ce qu’il y a dedans.

        Enfin bon, chacun fait ce qui lui plaît, hein.
        • [^] # Re: À quoi ça sert…

          Posté par . Évalué à 5.

          C'est pourtant simple à comprendre, Los Alamos est un centre de recherche américain publique/militaire (la bombe H). Il dispose de super-calculateurs et d'expert en calcule numérique. Il suffit de lire l'historique :

          ----------
          Project Background

          The project was conceived in 1996 by Dr M. Galassi and Dr J. Theiler of Los Alamos National Laboratory.

          They were joined by other physicists who also felt that the licenses of existing libraries were hindering scientific cooperation.

          Most of the library has been written by a relatively small number of people with backgrounds in computational physics in order to provide a consistent and reasonably-designed framework.
          ----------

          C'est pour ça que c'est du C avec une fonction pour le type float, double => optimisation maximale du temps de calcule.

          Boost est fait pour les adorateurs du code bloat. C'est pas la même problématique.

          Leur but était de réimplémenter en C et libre de droit tout un tas de codes FORTRAN qui traînaient sur les sites académiques.

          Discuter avec GSL n'a pas de sens, cette bibliothèque a été conçu aux petits oignons pour simuler des processus physiques, pas pour crypter.

          À chaque usage son outil. Point barre. Tu peux l'utiliser pour en faire ce que tu veux, mais tu ne changeras pas une ligne de codes dedans. La partie générateur de nombres est ultra-critique et sert de base à pleins d'algorithmes fournis par la bibliothèque.
    • [^] # Re: À quoi ça sert…

      Posté par . Évalué à 4.

      Mouais, enfin, GSL est sous GPL et donc inutilisable par un projet BSD.
  • # Mersenne twister

    Posté par . Évalué à 3.

    Moi qui croyait que Mersenne_Twister n'était pas cryptographiquement sécurisé ?
    • [^] # Re: Mersenne twister

      Posté par . Évalué à 6.

      C'est vrai, et il suffit de connaître
      1) l'algorithme utilisé (Mersenne-Twister ou autres)
      2) une suite de quelques nombres générés par l'algorithme
      pour savoir retrouver l'état interne du générateur et donc être capable de prédire les nombres suivants.

      C'est pour ça que les recommandations pour un usage cryptographique imposent d'ajouter en plus un "retraitement" de l'aléas généré. C'est-à-dire, appliquer une fonction de hachage sur la sortie permet d'empêcher l'utilisateur d'avoir accès à la sortie brute de l'algorithme et donc de pouvoir le prédire.

      Ensuite il y a des subtilités, genre parfois il vaut mieux ne prendre que quelques bits de la sortie de la fonction de hachage, etc...

      Voir http://www.ssi.gouv.fr/site_documents/politiqueproduit/Mecan(...) pour plus de précisions.
  • # initialisation

    Posté par . Évalué à 5.

    Pour mon information personnelle, pourquoi est-ce un probleme d'initialiser le generateur avec time(NULL) ?
    • [^] # Re: initialisation

      Posté par . Évalué à 6.

      Si on a une idée de quand le soft a été lancé, par exemple dans un intervalle de 100 secondes, on doit pouvoir essayer les 100 seeds possibles pour trouver la bonne. Pour savoir quand le soft a été lancé, si on a un accès local à la machine, il suffit de faire un top.

      (Disclaimer: je ne sais pas si c'est la faille principale, c'est juste la plus évidente. C'est pour ça qu'en général on rajoute au moins le pid au résultat de time, mais le pid est aussi public si on a un accès local à la machine.)
      • [^] # Re: initialisation

        Posté par . Évalué à 3.

        Ici on mélange tout et n'importe quoi comme déjà dit, et c'est dangereux.

        Il faut différencier les CSPRNG des PRNG. Initialiser correctement un PRNG on s'en fou puisqu'on peut assez facilement trouver l'état interne, et donc tout les états suivants, du générateur à partir de sa sortie. De mémoire pour un mersenne twister c'est dans les 8Ko.

        Au passage si quelqu'un à des références sur des PRNG parallèles (voir une jolie implémentation en java) ça m'intéresse. J'ai pas réussi a mettre la main sur des versions distribuées (sans contention après l'initialisation) et prouvées. La ce serait une contribution intéressante.
        • [^] # Re: initialisation

          Posté par (page perso) . Évalué à 4.

          Je vais essayer de répondre à toutes les critiques ou questions dans les commentaires.

          Effectivement, il y a globalement deux usages des générateurs de nombres pseudo-aléatoires : les simulations et la sécurité. Je ne connais pas trop les besoins en simulation, je dirai que l'algorithme doit être rapide. Tandis qu'en sécurité, on recherche un générateur le plus fidèle possible à un générateur réellement aléatoire, tant pis s'il est lent (ex: /dev/urandom vs /dev/random).

          OpenSSL et libgcrypt ont d'excellents générateur pour la sécurité, mais n'utilisent pas de base commune de code. C'est dommage car un bug impactant les deux bibliothèques ne sera pas forcément corrigé dans les deux. De même niveau fonctionnalité, si on rajoute une nouvelle source d'entropie dans l'une, l'autre ne saura pas l'exploiter.

          Mon idée serait donc de concentrer les efforts pour factoriser le code et donc avoir un maximum de sources d'entropie, beaucoup d'algorithme, et surtout un code bien testé. Pourquoi ne pas réutiliser GSL (ou autre) ? Je pense que le problème est qu' « on » n'a pas envie de tirer une grosse dépendance juste pour un sous-ensemble d'une bibliothèque. Maintenant si Hasard devient aussi gros qu'OpenSSL ou GSL, retour à la case départ :-) La licence BSD et un code écrit en C avec de nombreux bindings pourrait aider à l'intégration dans les autres projets.

          Au sujet de ma phrase « Je pense donc récupérer les meilleurs morceaux d'OpenSSL, libgcrypt, et autres (ex: GSL) pour faire une bibliothèque dédiée. Puis en suite, propose à ces projets de réutiliser mon code. », je me suis mal exprimé. Le but est de permettre à OpenSSL d'utiliser les meilleurs bouts de libgcrypt, et inversement !

          Bien sûr, il y a des problèmes de licence. J'ai contacté l'auteur de Mersenne Twister pour savoir si je peux utiliser la licence BSD et il m'a dit pas de problème. ISAAC est aussi compatible BSD (c'est dans le domaine public !). Pour RANDU, Park-Miller et drand48, je n'ai finalement réutiliser que des constantes, et je pense qu'elles sont dans le domaine public vu combien elles sont répendues.

          Niveau sécurité, Hasard n'est pas prêt pour générer des clés SSH ou certificat X.509. Les algorithmes implémentés ne sont pas sûrs et le code n'est pas assez testé. J'ai implémenté les algorithmes libres trouvés sur Internet. D'autres viendront plus tard. C'était un peu une preuve de concept pour savoir si ça peut intéresser du monde. J'aimerai -si possible- réunir le meilleur des deux mondes, simulation et sécurité, pour factoriser les efforts.
          • [^] # Re: initialisation

            Posté par . Évalué à 4.

            Ma critique c'est que tu as des objectifs de sécurité et dans hasard je vois pas mal de PRNG qui ne sont clairement fait que pour les simulations... Bref pour le moment ça ne sert pas a grand chose. Si ce n'est au pire de faire croire a une utilisateur qu'il peut utiliser ces générateurs de manière sure.

            Et bien évidement pour tes objectifs GSL t'es totalement inutile. Pour le côté simulation il y a déjà des lib qui sont reconnues et auditées donc pas trop de besoins (sauf pour les générateurs parallèle).

            Après il faut voir si il y a vraiment un besoin pour les CSPRNG et se borner a ça. Mais la il vaut mieux avoir du manpower compétent en cryptographie. Peux tu prouver que la façon dont tu initialises les PRNG ne les affaibli pas (théoriquement et implémentation) ? La faille d'OpenSSL^wDebian c'était une ligne commentée d'un code fait par des experts et modifiée par un maintainer...
            • [^] # Re: initialisation

              Posté par . Évalué à 5.

              Je me permet d'appuyer ce commentaire très fortement. Il faut différencier deux choses : les générateurs aléatoires pour la sécurité et les générateurs aléatoires pour le reste du monde. Parler de Mersenne Twister pour la sécurité, c'est idiot, c'est un générateur qu'on peut prédire (bon, c'est pas trivial mais ça se fait). Quand je vois aussi qu'on parle de /dev/random, au bout d'un moment, c'est un bête générateur congruentiel linéaire (qui se casse presque à la main), /dev/urandom est un peu mieux. Donc ne mélangeons pas tout.

              Victor: je crois qu'il n'y a pas de place pour ton projet, parce que comme dit précédemment, soit tu te focalises sur les générateurs pour la sécurité et alors il te faut des armes mathématiques pour comprendre ce que tu fais ainsi que des armes informatiques pour bien le faire (et OpenSSL le fera mieux que toi). Soit tu te focalises sur les générateurs pour le reste du monde mais là, tu vas te casser la tête pour rien vu que pour le reste du monde, rand() ou même un Mersenne Twister (qui va être dans la stdlibc++) suffise amplement.
              • [^] # Re: initialisation

                Posté par . Évalué à 4.

                Quand je vois aussi qu'on parle de /dev/random, au bout d'un moment, c'est un bête générateur congruentiel linéaire (qui se casse presque à la main), /dev/urandom est un peu mieux.

                Heu, c'est le contraire, /dev/urandom c'est la version rapide et /dev/random c'est la version qui attend de récupérer suffisamment d'entropie pour générer les octets suivants.
          • [^] # Re: initialisation

            Posté par . Évalué à 3.

            tant pis s'il est lent (ex: /dev/urandom vs /dev/random).

            Euh, ce n'est pas tout à fait vrai ça : si c'est vrai pour la génération de clefs asymétriques (qu'on ne fait pas tous les jours), pour les serveurs de signatures, les protocoles SSL, etc. où on utilise beaucoup de nombres aléatoires à usage unique (nonces ou clefs de session), la vitesse du générateur pseudo-aléatoire commence à avoir une influence importante.
  • # GSL est vraiment pas mal

    Posté par (page perso) . Évalué à 3.

    Slt,

    Par expérience je me demande si tu as conscience Victor à ce que tu t'attaques. Non pas pour te démoraliser ou autres choses, mais j'ai l'impression que tu as une vision simpliste sur laquelle tu t'attaques.

    Récemment je me suis posé la même question que toi. J’avais besoin de faire quelques simulations pour valider quelques travaux de recherches (dans le domaine des bases de données). J’avais besoin d'un volume important de données non corrélé (sinon très très peu).

    Il est vrai que pour qlq'un qui recherche un générateur de nombre aléatoire, le premier réflexe est d'utiliser Rand() qu'on a par défaut sous c (et C++) dans différentes bibliothèques (glibc entre autres). Mais des qu'on cherche qlq chose de plus sophistiquée on n'a pas systématiquement le reflète de ce dire qu'il y' a forcement une bibliothèque pour cela. Je me disais avec une naïfté qui n'a pour égale que mon... ; que c'était qlq chose de ne pas si compliqué que sa. Mais rapidement j'ai déchanté. Car un bon générateur, bien implémenté doit vérifier certaines propriétés mathématiques (non corrélation, périodicité grande, etc.). Les labiraintes théoriques ont eu raison de ma volonté. Surtout au niveau de la validation d'une implémentation.

    Puis je suis tombé sur GSL. Et je dois dire qu'elle est très bien foutue (conception très factorisée en autres).

    Donc, je n'aurais qu'une chose à dire à Victor. Ta démarche est louable, mais tu as le choix entre une contribution intégré à GSL qui sera directement utile à une communauté déjà établie. Ou la grande traversée nécessitant environ une décennie pour avoir une bibliothèque mature et reconnue.
    • [^] # Re: GSL est vraiment pas mal

      Posté par . Évalué à 2.

      Il est vrai que pour qlq'un qui recherche un générateur de nombre aléatoire, le premier réflexe est d'utiliser Rand() qu'on a par défaut sous c (et C++) dans différentes bibliothèques (glibc entre autres).

      J'ai pas l'habitude de coder en C, mais pour de grand volumes de données mon premier réflexe aurait plutôt été /dev/random (pas urandom dans ton cas puisque tu parle de données non corrélée). Un petit coup de dd et tu as la quantité de données que tu veux.
      • [^] # Re: GSL est vraiment pas mal

        Posté par . Évalué à 2.

        Oui mais la ta simulation va prendre 1 mois au lieu d'une heure. C'est tout l'intérêt des différents PNRG et de leur propriétés: être très rapide en répondant aux spécifications. Les simulations reposant sur des PRNG consomment des volumes énormes de nombre aléatoires.

        Cela dit tu n'as jamais fait de dd avec /dev/random comme source apparemment. Autrement tu saurais comment il se comporte quand le noyau est a cours d'entropie :-)
      • [^] # Re: GSL est vraiment pas mal

        Posté par . Évalué à 4.

        Mouais, pour un grand nombre de données /dev/random va quand même pas très vite (Pour ne pas dire que c'est carrément super lent).

        # dd if=/dev/random of=/dev/null
        0+140 records in
        2+0 records out
        1024 bytes (1.0 kB) copied, 497.191 s, 0.0 kB/s


        Alors, la quantité que tu veux, oui. Mais uniquement si tu as beaucoup beaucoup de temps.
        • [^] # Re: GSL est vraiment pas mal

          Posté par (page perso) . Évalué à 1.

          la lenteur de /dev/urandom n'est pas la seule raison (mais la première). la portabilité aussi. même si un équivalent existe sous la plupart des systèmes. la plupart nécessite une implémentation spécifique.

          enfin bon. on peut en débattre encore et encore.
  • # Une faille ?

    Posté par . Évalué à 2.

    C'est quoi le problème avec "rand()%nombre pour générer un nombre dans l'intervalle [0; nombre-1]" ?

    Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

    • [^] # Re: Une faille ?

      Posté par (page perso) . Évalué à 4.

      Lit la partie "NOTES" de la page de manuel de la fonction rand(). Extrait : « Ceci n’est pas le cas avec les anciennes implémentations ...) où les bits de poids faibles n’étaient pas « aussi aléatoires » que ceux de poids forts ». En gros ça donne un truc du genre :
      http://www.random.org/analysis/dilbert.jpg
      • [^] # Re: Une faille ?

        Posté par . Évalué à 4.

        Et puis, même si RAND_MAX est grand, quand tu veux un nombre entre 0 et 4, tu lances un dé et tu fais un modulo 4 ?

        (indice : un dé donne (1, 2, 3, 4, 5, 6), soit (0, 1, 2, 3, 0, 1) avec un %4.)
        • [^] # Re: Une faille ?

          Posté par (page perso) . Évalué à 2.

          Une page de man de rand précise que, dans In Numerical Recipes in C: The Art of Scientific Computing, il est conseillé :
          "If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in
          j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));
          and never by anything resembling
          j = 1 + (rand() % 10); (which uses lower-order bits)."

          Mais ceci n'est vrai que pour les anciennes implantations de rand. Donc, maintenant, dans la vraie vie, le modulo est suffisant pour les applications utilisant rand, qui n'ont de toute façon pas forcément besoin d'une forte source d'aléas.

          Ensuite, concernant l'exemple du dé, j'aimerai connaitre un processus déterminister qui fait mieux que le modulo pour la répartition :) D'ailleurs, si RAND_MAX est un multiple de 4, tout se passe bien !
          • [^] # Re: Une faille ?

            Posté par (page perso) . Évalué à 2.

            int
            rand4(void)
            {
                    int d;
                    while ((d = dice()) > 4)
                            ;
                    return d;
            }
            Cette fonction fini presque surement en un temp infini.
            • [^] # Re: Une faille ?

              Posté par (page perso) . Évalué à 3.

              Élégant !
              Je me limitais à un tir de dé, mais c'est vrai que ta solution est belle. Puis j"ai toujours été fan de ce genre de fonctions qui terminent avec probabilité 1 sans qu'on puisse en dire plus :).
              • [^] # Re: Une faille ?

                Posté par . Évalué à 2.

                En l'occurrence on peut en dire plus : on peut calculer l'espérance de la durée d'exécution de cette fonction avant qu'elle s'arrête, l'écart-type de la distribution des durées d'exécutions sur plusieurs essais, etc...

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.