Discussion :

[cs_ntd]

Bonjour à tous,

Après la lecture du cours sur "Les nombres aléatoires en C" (http://nicolasj.developpez.com/articles/libc/hasard/), ainsi qu'un (rapide) examun des autres méthodes de génération (Blum Blum Shub, Fibonnacci, Mersenne Twister, Von Neumann...) une question me taraude...

Dans la plupart des exemples cités ci-dessus, et même pour les plus fiables d'entre eux (BBS apparement), on utilise les propriétés du modulo, ce qui rend dans certains cas de bon bons résultats, étant donné la longeur du cycle du modulo.

Mais qui dit cycle dit périodicité des résultats, ou du moins possibilité par l'analyse de déceler une imperfection.

Dans ma grande prétention, j'ai pensé à une autre méthode pour créer des une suite de nombres qui n'est point périodique, ou du moins, mathématiquement parlant, la périodicité n'est pas prouvée.

Tout repose sur le principe des suites logistiques (wikipédia présente cela très bien: http://fr.wikipedia.org/wiki/Suite_logistique).

Une suite logistique est de la forme v(n+1) = µv(n)(1 - v(n)). Elle nécessite deux paramètres de départ : µ et v(0).

Cette suite présente la propriété de diverger pour presques toutes les valeurs de v(0), pour µ aux alentours de 4 (sauf cas particuliers "évidents" ou liés au théorème de Sarkovskii).
En réalité, il y a donc non-périodicité des résultats (ou une période "infinie") si les conditions ci-dessus sont respectées (µ ~= à 4 et v(0) non particulier).

De plus, et c'est lié entièrement à la "théorie du chaos" (), une petite variation sur les conditions de départ peut entraîner (et même entraîne) de grandes variations sur les résultats.

La "non-cyclicité" des résultats et sa grande sensibilité aux conditions initiales ne pourrait-elle donc pas être utilisée à des fins de générations aléatoire des nombres ? J'ai l'impression que cela repose sur un principe plus fiable que le modulo. On pourrait même ensuite imaginer sélectionner certaines décimales suivant un algorithme, ce qui rendrait différent les résultas obtenus pour des conditions initiales similaires.
On peut aussi envisager de jouer sur le terme de la suite (et ne pas forcemment commencer à v(1) )

Comme le dit wikipédia: au bout d'un certain temps, un phénomène chaotique est devenu imprévisible alors même que la loi qui le définit est parfaitement déterministe (idéal pour les ordinateurs non ?).

Qu'en pensez-vous ?

Le seul inconvénient que je pourrait voir, est que l'on ne travaille plus avec des entiers, mais avec des décimaux. Mais est-ce "si" dérangeant ? les calculs ne sont pas d'une difficulté redoutable non plus...

Voilà quelqu'un saura-t-il me dire ou je commet une erreur, ou bien ou est-ce que cela n'est pas faisable? Ou pourquoi personne n'utilise cette méthode alors...

J'attend vos réponses avec impatience !

[benDelphic]

ben , ce que tu cite comme étant un avantage , ne l'est pas ... pour toutes les méthode que tu as cité on s'arrange toujours pour avoir une trés grande période ...
ce que tu appelle V(0) est dit seed ou graine ... et tu vois bien que v(0) influe sur la séquence mais pas sa convergence ... d'autant plus que comme tu le dis

Le seul inconvénient que je pourrait voir, est que l'on ne travaille plus avec des entiers, mais avec des décimaux. Mais est-ce "si" dérangeant ? les calculs ne sont pas d'une difficulté redoutable non plus...

tu néglige l'aspect technique , ordinateurs ... etc, et puis tu es sur que la suite diverge ? et si un élément de la suite s'annule ?

[smyley]

Mais si on trouve un moyen d'obtenir le seed de départ ou certaines valeurs, on pourrai essayer de retrouver l'expression de la suite et on pourrai prévoir les valeurs suivantes non ?

[FR119492]

Salut!
L'ordinateur étant un engin déterministe (même si ça n'est pas toujours évident!), il n'est pas capable de produire une suite véritablement aléatoire. Les générateurs usuels ne délivrent que des suites pseudo-aléatoires, ce qui est largement suffisant par exemple pour la simulation de processus industriels, mais pas en cryptologie. Lorsqu'on veut une suite ne présentant aucune périodicité, on utilise un phénomène physique supposé aléatoire (bruit thermique, radioactivité, etc.).
Jean-Marc Blanc

[cs_ntd]

Bien, merci à tous pour vos réponses! alors, dans l'ordre:

benDelphic:

pour toutes les méthode que tu as cité on s'arrange toujours pour avoir une trés grande période ...

Mais qui dit période dit qu'il y a une possibilité non négligeable de trouver ce cycle.

ce que tu appelle V(0) est dit seed ou graine ... et tu vois bien que v(0) influe sur la séquence mais pas sa convergence ...

Je ne comprend pas bien ce que tu veux démontrer par là... v(0) ne va certe pas influer sur le nombre des valeurs d'adhérence, et on a théoriquement pour 2 v(0) distincts une même convergence... Sauf que pour un µ ~= 4, on est dans l'incapacité mathématiques de prévoir ces valeurs d'adhérence. Donc...

tu néglige l'aspect technique , ordinateurs ... etc

Tant que ça ? Un ordinateur n'est donc pas capable de calculer très rapidement avec ne serait-ce qu'avec 10 décimales?

et puis tu es sur que la suite diverge ? et si un élément de la suite s'annule ?

Il n'y a que si v(0) = 0 que la suite s'annule pout tout v(0) (elle est même constante et vaut tout le temps 0). Sinon, il y a d'autres valeurs spéciales en fonction de µ.
Si par exemple µ = 4, on ne doit donc pas prendre (en plus de 0) les valeurs 0,25 0,5 0,75 par exemple, pour des questions de symétrie etc... (si v(0) = 0,25 ou 0,75, la suite converge vers 0,75. Mais même 0,249999999999999 ne converge plus vers 0,75...) (et si v(0) = 0,5, la suite va s'annuler (mais que dans le cas ou µ = 4).

Sinon je ne connait pas la formulation exacte pour le dire, mais je vais l'énoncer comme ça: pour µ=4, la suite à une infinité de valeurs d'adhérence (on ne parle de convergence que pour une seule valeur).
Or sauf cas très particuliers, il est démontré que plus µ augmente, plus le nombre de valeurs d'adhérence augmente.
Je ne sais pas si c'est véritablement exact mathématiquement parlant, mais ce qui est sur, c'est que l'on est dans l'incapacité de prédire les valeurs d'adhérence, et d'y voir une cyclicité.

On ne pourra donc pas dire que lim(n -> +inf) v(n + k) = a, même après une infinité de termes. Ce qui est possible avec d'autres valeurs plus petites de µ (par exemple 1).

smyley:

Mais si on trouve un moyen d'obtenir le seed de départ ou certaines valeurs, on pourrai essayer de retrouver l'expression de la suite et on pourrai prévoir les valeurs suivantes non ?

Ce que tu dit est très juste: la connaissance de valeurs (termes, ou µ) est suffisante pour déterminer µ, et bien que je ne l'ai pas expérimenté, je ne pense pas trop m'engager en disant qu'il est possible "d'inverser" la suite pour remonter le fil des valeurs. Néanmoins, on ne peut pas réellement trouver v(0), car on ne saura pas quand s'arrêter ! (sauf cas particuliers, qi'il est possible d'éviter, passons).

Et tu oublis une chose, c'est que l'ordinateur ne calcule pas de valeurs exactes... ce qui implique que:

1) on a pas les valeurs exactes, du fait qu'un oridnateur ne fait pas de calcul exact.

2)"l'utilisateur" n'est pas censé savoir l'index des termes...

Du fait de la très grandes sensibilité au conditions initiales, une erreur de 0,00000000000000000001 peut entrainer des résultats totalement faux (je détaille pas tous les cas, ceux dans lesquels ont peut approximer localement le comportement prochain par exemple, etc... et qui sont facile à éviter).
Tout un tas de petits paramètres liés au fonctionnement de l'ordinateur rentrent aussi en compte et ajoute de la difficulté au "casseur" (nombres de chiffres significatifs, etc...)

Et on n'est pas non plus obligé de donner les termes: imagine qu'en plus, pour construire un nombre aléatoire, on prenne la 4ième déciamle d'un terme, puis pour le deuxième chiffre du nombre, on prenne la 4ième décimale d'un autre terme, ainsi de suite.
Et c'est tout de suite plus dur à casser .

Je pense qu'on là atteint un niveau de non-déductibilité véritablement conséquent...


FR119492:

Salut!
L'ordinateur étant un engin déterministe (même si ça n'est pas toujours évident!), il n'est pas capable de produire une suite véritablement aléatoire. Les générateurs usuels ne délivrent que des suites pseudo-aléatoires, ce qui est largement suffisant par exemple pour la simulation de processus industriels, mais pas en cryptologie. Lorsqu'on veut une suite ne présentant aucune périodicité, on utilise un phénomène physique supposé aléatoire (bruit thermique, radioactivité, etc...).
Jean-Marc Blanc

En réalité, c'est effectivement pour des applications en cryptologie que je me renseigne sur les méthodes de génération aléatoire de nombres. Mais comme tout le monde n'a pas la chance d'avoir de l'uranium chez soi , et qu'on ne peut donc pas faire de mesures, peut tu détailler comment utiliser ces phénomènes? (de mémoire, j'ai toujours entendu qu'ils sont aléatoires, mais n'y a t-il pas confusion entre aléatoire et imprévisible? Je ne suis malheureusement pas assez au point sur la désintégration de l'uranium pour pouvoir trancher )

Cependant, oui je suis au courant du fait que quoi que je fasse, je ne génererais pas une suite parfaite de nombre aléatoire, mais j'essaye (du bas fond de mes connaissances ) de perfectionner ce qui existe déjà (l'optimisme est développé chez moi ).

Sinon:

Mais comme personne n'est à l'abris d'une idée géniale , je poste mes idées ici en voyant si quelqu'un arrive à démonter ce que je dit. Il est fort probable que je fasse des erreurs d'interprétation sur les suites logistiques, ou que j'oublis un détail qui ait malgrès tout son importance.

Je ne suis malheureusement pas un spécialiste des modulo, (ni des suites logistiques hélàs), ce qui fait que je ne me pense pas apte mathématiquement parlant, à démontrer quelque chose là dessus, même si je pense avoir raison .

En fait, je n'ai pas trouvé d'exemple de génération avec ces suites, et c'est ce qui me perturbe. On dirait que personne n'y a pensé
On fait état de méthodes qui ont largement prouvées leur innaptitude. Alors même si la mienne était bidon, pourquoi personne ne la mentionnerait ? surtout que j'ai l'impression d'avoir fait un générateur correct...

Donc si quelqu'un à entendu parlé de ça un jour, qu'il le dise !

Et mon problème et donc de savoir si il y a une faille dans ce que je dit (dans mon interprétation du modulo ou des suite logistique).

Encore merci à tout ceux qui ont pris et prendront la peine de me répondre

[pseudocode]

Donc si quelqu'un à entendu parlé de ça un jour, qu'il le dise !

http://www.google.com/search?q=rando...er.ist.psu.edu

Et mon problème et donc de savoir si il y a une faille dans ce que je dit (dans mon interprétation du modulo ou des suite logistique).

Un bon générateur aléatoire pour la crypto doit générer constament des sequences ayant des caracteristiques particulières (entropie, compléxité, probabilité, corrélation ...).

Avec les systèmes usuels (congruentiel linéaire, ...) c'est deja très dur de "prouver" que ces caracteristiques seront toujours respectées. Avec les systèmes chaotiques, ca doit être pire.

[Jean-Marc.Bourguet]

Tu as un système déterministe qui stocke son état dans un nombre fini de bits. Quelle que soit la manière dont tu calcules l'état suivant, le nombre d'états étant fini, ta séquence va obligatoirement finir par boucler. Tu auras un cycle dont la taille maximale est donnée par 2^nombre de bits dans l'état.

Les méthodes classiques ont été analysées pour être sûr de différentes caractéristiques -- comme l'équirépartition ou une difficulté à trouver la valeur suivante à partir des valeurs passées -- qui dépendent en partie de l'utilisation -- cryptographie ou autre. Je suis loin d'être sûr que les suites logistiques aient ces caractéristiques. Et sans pouvoir prouver qu'elles les ont, tu as quelque chose d'inutilisable.

[FR119492]

Salut!
Finalement, tout dépend de ce que tu veux faire avec ta suite de nombres dits "aléatoires":

1. C'est pour ton plaisir ou pour ta satisfaction intellectuelle.
2. C'est un exercice et ton prof examinera le "source" du programme que tu auras écrit.
3. C'est encore un exercice, mais ton prof n'aura accès qu'à la séquence générée.
4. Tu veux ou tu dois mettre au point un système de chiffrage que même la NSA n'arrivera pas à casser.

Dans le cas 1, l'ordinateur ne peut t'apporter aucune solution, vu qu'il est parfaitement déterministe.

Dans le cas 2, tu donnes la réponse ci-dessus à ton prof.

Dans les cas 3 et 4, c'est à toi d'inventer quelque-chose de suffisamment tordu. Je te propose par exemple la solution suivante: tu prends une photo d'un tapis persan ou des vitraux de la cathédrale de Reims, et tu la numérises en un format non compressé (tiff ou bmp). Tu obtiens un fichier qui contient une suite d'octets. Tu en supprimes un certain nombre, au piffomètre, de manière à ce que la longueur de ce qui te reste et la période d'un générateur par congruence linéaire soient premières entre elles.
Soient X(i) les octets provenant de ton tapis et Y(k) les octets provenant de ton générateur. Tu démarres avec un W(1) et un Z(1) choisis comme tu veux. Tu construis ensuite les suites
W(2)=X(1+Z(1))
Z(2)=Y(1+W(1))

W(3)=X(1+Z(2))
Z(3)=Y(1+W(2))

etc.

Si tu as l'impression que ton prof ou la NSA a cassé ton algorithme, achète un autre tapis ou va faire un tour à Chartres.

Jean-Marc Blanc

PS: Attention! Peut-être que ton prof et la NSA surveillent ce forum!

[droggo]

Jie,

Il y a des tas de personnes extrêmement qualifiées qui travaillent sur ce thème, à plein temps pour une bonne partie, et je pense que si ta solution était meilleure que ce qui existe déjà, et bien, elle ferait partie du "existe déjà".