Fonction aléatoire

[invitea08bfa58]

Bonjour à tous !

J'ai hésité à poster ce sujet, donc si il vous semble placé dans la mauvaise catégorie, modérateurs, mea culpa.

Je souhaiterais avoir des informations concernant la fonction dite "aléatoire", c'est-à-dire permettant de générer un réel de façon complètement aléatoire.

Je suppose que, malgré tout, ce réel ne sera pas compris dans l'intervalle , puisque la mémoire d'un ordinateur n'est pas illimitée.

Merci pour votre attention,
Mikro.

Bonjour Mikro
Votre question semble concerner la programmation; en bon franglais-hexagonal: "software".
Je vous redirige vers cette section.

La modération
Papykiwi
-----

[invite4ad25ccf]

Les fonctions génératrices de nombres aléatoire n'existent effectivement pas en informatique. On parle de nombre pseudo aléatoire.
Un nombre pseudo aléatoire peut etre définit comme une suite de bits de taille définit dont les propriétés de génération du nombre suivant semble aléatoire.

Ce nombre est compris entre 0 et 2^32 pour un entier non signés sur une architecture 32bits.
Pour avoir des nombres "aléatoire" allant de - inf à +inf, on peut utiliser les flottant sur 32 ou 64bits. On obtient ainsi un grand nombre, mais pas forcément précis

Les fonctions aléatoire basique utilisée en informatique sont généralement des suites prédéfinies initialisés avec une graine. Ainsi si deux personnes utilisent la meme graine, alors ils obtiendront la meme suite aléatoire

La génération de "vrai" nombre est très compliqué, généralement réservé aux cryptographes, qui ont le plus besoin de nombre le plus aléatoire possible. Par exemple, le NIST (organisme définissant les standards US dans les TI) définit 4 fonctions de génération de nombre pseudo aléatoire considérées comme sures :
- une basée sur les fonctions de hashage
- une basée sur les fonctions HMAC()
- une sur le chiffrement par bloc
- une sur les courbes elliptiques [1]

Pour plus d'informations :
- http://fr.wikipedia.org/wiki/G%C3%A9...l%C3%A9atoires
- les pages de manuels random(3) http://www.linux-kheops.com/doc/man/.../random.3.html et urandom(4) http://www.linux-kheops.com/doc/man/.../random.3.html


[1] : L'ajout de cette fonction à été poussée par la NSA, bien qu'elle soient plus lente. A la conférence CRYPTO' 2007, Dan Shumow et Niels Ferguson ont démontré que celle ci contenait une faille et qu'il était possible de retrouver toute la suite a partir d'une toute petite sous suite. ( voir le blog de Schneier : http://www.schneier.com/blog/archive...nsa_watch.html)

[invitea08bfa58]

Alors, alors :

Si j'ai bien compris, la fonction aléatoire doit obligatoirement comencer par une suite définie (la graine) pour ensuite générer des nombres pseudo-aléatoires ?
Et si la puissance du générateur est limitée, on retombera forcément sur la suite "mère", c'est-à-dire la graine ?
Et de toute façon, même en 64 bits, on n'obtiendra pas un nombre réellement compris entre puisque, même si la puissance d'un 66 bits est élevée, elle n'est pas infinie...

Du moins, c'est mon point de vue.

Scientifiquement,
Mikro.

[invite4ad25ccf]

En fait tout dépend des besoin d'aléat. Mais il est clair qu'un jour on retombera sur la même suite et que l'on arrivera jamais à faire un nombre réel entre -inf et +inf, car de toute facon, un tel nombre n'existe pas en informatique Ce que l'on fait de mieux c'est générer une suite de N bits aléatoires.
Dans mes exemples, j'ai pris 32 / 64 car c'est les fonctions que l'on trouve le plus fréquement utilisés dans les applications (jeux, programmes).
Dans la crypto, ils sont généralement un peu plus grand, ceux pour la génération à partir de courbe elliptiques sont par exemple 256 / 384 ou 521 bits.
Il faut aussi savoir que l'on considère que retrouver un nombre de 2^80 bits par énumération des cas est considéré comme impossible. Donc si la génération de la graine est bonne, il est "impossible" de retrouver la suite sans toutes les énumérer.

Dans un programme "simple", il n'est pas forcément intérressant d'avoir une suite pseudo aléatoire unique. Le plus interressant est qu'il soit difficile de retomber sur celle ci par hasard (cas de vieux jeux qui initialisait toujours la suite avec 0, le dé faisait donc toujours les mêmes lancés )
Dans un programme de génération de clés de chiffrement, il est necessaire que les fonctions soient cryptographiquement sures. Dans ce cas, on peut utiliser différents outils pour générer la graines la plus aléatoire possible. De tels outils coutes chers en temps :
- on utilise une carte qui capture le bruit électromagnétique que l'on converti en nombre
- sous linux, urandom est initialisé grace aux paramètre fournit par l'entropie du noyaux, se basant sur les touches pressés, l'interval entre les frappes, les paquets réseaux recus, ...
Pour obtenir une bonne graine avec ces processus, il devient donc nécessaire d'attendre "longtemps" d'ou le fiat qu'on ne les utilises pas pour générer a chaque fois un nombre aléatoire, mais une suite de nombre pseudo aléatoire.

[A voir en vidéo sur Futura]

[polo974]

...
Je suppose que, malgré tout, ce réel ne sera pas compris dans l'intervalle , puisque la mémoire d'un ordinateur n'est pas illimitée.
...

Attention, avec les réels (float ou double ou ...).
Comme leur représentation est de la forme mantisse X 2^exposant,
la distribution de l'aléa soit ne sera pas uniforme (algo ne tenant pas compte du format float utilisé), soit sera limitée à un sous-ensemble tel que l'exposant ne change pas (algo tenant compte du format float utilisé).
Et comme il existe des représentations de et , il est possible de récupérer des "nombres" infinis, tout comme d'ailleurs des NAN (Not A Number).

Par contre le nombre de combinaisons possibles reste toujours au mieux 2³² ou 2⁶⁴...

En float, 10²⁰ + 1 = 10²⁰... donc éviter de s'en servir pour générer une suite... et comme les pseudo aléatoires sont des suites...

[invite8b867113]

Pour générer une graine, la solution la plus simple est de récupéré l'heure système.

[invitea08bfa58]

Bonjour à tous.

Je peux constater que les informaticiens ne manquent pas d'idée pour générer des nombres aléatoires. Qui plus est, les cryptographes savent également très bien utiliser ces systèmes.

Générer une suite de nombres pseudo-aléatoires en 256 bits... comment cette suite peut-elle être reconstituée ???

Merci à tous pour vos réponses,
Mikro.

[invite4ad25ccf]

Un nombre n'est qu'une suite de bits. Qu'il soit sur 32, 256 ou plus ne change pas grand chose. Il est juste plus simple pour un ordinateur de faire des calculs sur 32bits puisqu'il est cablé ainsi (et 64 sur les archi 64bits ). Mais pour faire les calculs sur plus de bits, on acolle "juste" des nombres de 32 bits les uns à la suite des autres. Cela se fait très facilement en C avec les fonctions de la bibliothèque GMP par exemple (GNU multiple precision
arithmetic library)


Quand à reconstituer des séries sur 256bits, c'est pas plus dur que sur 32, c'est aussi difficile

Prenons par exemple la suite sur les courbes elliptiques (pages 57-68 : http://csrc.nist.gov/publications/ni..._March2007.pdf)

Les nombre utilisés pour définir cette courbe sont standard. Shumow et Ferguson ont démontrés (http://rump2007.cr.yp.to/15-shumow.pdf) que ces nombres avaient une relation avec une autre suite de nombre, secret, qui peuvent servir de "clé secrète". Si l'on connait ces nombres secret, on peut prédire la sortie du générateur de nombre pseudo aléatoire à partir de seulement 32bits de données.
Il est donc possible de déchiffrer n'importe quelle communication utilisant ce générateur si l'on connait ces nombres, l'algo faisant partie des 4 algos officiels retenu pour la génération de clés.

La cryptographie reposant énormément sur la génération de nombre aléatoire, il s'agit donc d'un sujet très pointu et très à la mode

[invitee1ee630d]

Tous ces messages me rejouissent, je ne suis pas le seul à trouver ce sujet passionant.Mais qui dit passionné ne dit pas pas instruit, et j'avoue ne pas tout comprendre de ce qui s'est dit malgré de nombreuses lectures sur le web.

voici ce qui me choque:
Pour ce qui est de l'informatique on part d'une graine qui est determinée, obtenue par exemple par le nombre de miliseconde depuis lequel est lancé Windob.
Mais pourquoi ne pas se contenter de ce nombre??
C'est surement une grossiere erreur de ma part mais je ne vois pas la difference entre appliquer à cette graine une multiplication par 10 et entre l'appliquer à la suite de Fibonacci.

[invite4ad25ccf]

Tout dépend de ce que tu recherches comme fonction aléatoire.
Prenons par exemple un jeu de poker online. Les cartes sont tirées aléatoirement.
Si on prend l'uptime du serveur comme tu le suggère, on sera à même de deviner, après un certains nombre de partie l'uptime, et donc la suite. Et une fois que l'on a la suite, il suffit de la parcourir pour savoir quand jouer, voire connaitre les jeux des autres.

Rien que cet exemple banal montre qu'il est interressant que les fonctions soient le plus aléatoire possible. Et je ne parle meme pas des nombre générés pour sécurisé les transactions banquaire, la ça serait la cata si on arrivait a casser la fonction aléatoire

[invitee1ee630d]

Ah ca devient plus clair.En gros pour engendrer un nombre pseudo aléatoire il faut:
-une graine determinée par des phénomènes physiques ou informatiques
-appliquer une suite à cette graine afin "d'écarter" au plus le resultat de la graine.

Je conçois que cette derniere étape soit primordiale à partir du momment où la graine est previsible.Mais si elle ne l'est pas ,il n'est (rassurez moi) plus utile d'appliquer cette graine à une suite.

j'ai maintenant d'autres interrogations:
-on parle de suite, mais alors pour en determiner un nombre pseudo aleatoire quelles restrictions doit-on prendre?C'est à dire quelles valeur donner à U0 et U1 ou encore quel nombre d'itterations doit on faire pour s'assurer d'éloigner le resultat de la graine.Comment éviter les nombres absorbants...
Et surtout quelles suites sont les plus fiables!
Une suite ne demandant pas de definir u1 mais seulement u0 n'est -elle pas moins restrictive offrant alors un resultat moins biasé?..

ps:Merci pour tant de clarté que je m'efforce de reproduire

[invite4ad25ccf]

Les suites ne sont pas définies dans R, mais dans des groupes différents (par exemple celui des courbes elliptiques : http://fr.wikipedia.org/wiki/Courbe_elliptique ) et ne se modélise pas tout à fait de la même facon :

En général il s'agit d'une fonction qui dépend de deux paramètre : la graine (qui est souvent regénérée à chaque itération) et d'un paramètre "aléatoire" (le nombre d'interruption processeur, la date ....) pour donner l'élément suivant.
Un exemple d'une telle "fonction" peut etre trouvé sur http://csrc.nist.gov/publications/ni..._March2007.pdf Figure 13 page 57 (fonction sur une courbe elliptique)

Après, je ne peux pas te donner plus de détail, ca dépasse de loin mon niveau en mathématique, je ne connais que la théorie. Pour des questions plus spécifiques, peut etre que le forum mathématique est plus approprié

[JPL]

Juste un détail : la graine peut parfaitement être imprévisible à l'échelle humaine compte tenu du type d'événement choisi par la générer, mais sans faire partie d'une suite de valeurs équiprobables. Exemple simple : si tu prends comme graine le nombre de millisecondes depuis que l'horloge de l'ordinateur a été initialisée, sur un clic tu ne peut pas prévoir ce nombre, mais ce dont tu es sûr c'est qu'au deuxième clic il sera plus élevé qu'au premier. C'est un peu caricatural mais ça permet de comprendre.