Générateur aléatoire

[fred3000gt]

J’ai cru comprendre qu’il n’y avait pas de générateurs aléatoires infinis non pèriodiques... mais les décimales de PI ne sont-elles pas un contre exemple? (Je ne juge pas de la qualité du générateur)
-----

[GBo]

Bonjour,
La suite des décimales de Pi n'est pas aléatoire : quel que soit le rang que tu me présentes, je peux te prédire la suivante.
Si tu en es à 3,141 par exemple, je peux te prédire avec certitude que le digit suivant sera 5.
-> Inutilisable comme générateur aléatoire (en crypto par exemple).
cdlt,
GBo

[fred3000gt]

Merci, mais je parlais naturellement des générateurs pseudo-aléatoires
Ils sont tous naturellement déterministes, la question est si les décimales de PI constituent un exemple infini et non-périodique?

[GBo]

Dans ce cas il fallait le préciser, c'est grave

[A voir en vidéo sur Futura]

[Deedee81]

Salut,

Les générateurs basé sur un calcul informatique ne sont jamais totalement aléatoire (c'est pour ça que l'on dit pseudo aléatoire) car basés sur un calcul déterministe bien que (volontairement) très difficile à prévoir sans exécuter le calcul qui peut être long si on génère un million de nombres par exemple. Un "bon" générateur est indispensable dans certaines techniques de cryptographie, on a parfois découvert des failles de cryptage qui venaient d'un "mauvais" générateur.

On améliore en utilisant une valeur de départ prise sur l'horloge, la température, etc... Cela n'est toujours pas aléatoire mais s'en est très proche ("proche" dans un sens quelconque, la complexité de Kolmogorov, l'entropie de Shanon, on utilise ce qu'on veut ).

On peut avoir un véritable système aléatoire mais à condition de se baser sur un phénomène physique réellement aléatoire, comme une désexcitation d'origine quantique (totalement aléatoire.... au moins pour ce qu'on en sait !). Mais beaucoup de systèmes se contenent du bruit de grenaille ou du bruit thermique très très proche de l'aléatoire.

Enfin, en mathématique, en effet les décimales de pi ne sont pas aléatoire, pas au sens où en l'entend ici en tout cas (il peut l'être au sens de "nombre normal" mais c'est différent et en plus.... non prouvé).

Mais l'aléatoire existe en math (je parle pas de la théorie des probas évidemment). Ainsi Chaitin avait pondu une équation diophantienne :
https://fr.wikipedia.org/wiki/Om%C3%...%C3%A9matiques
absolument incroyable (elle était aussi énorme, un bouquin entier, générée grâce à un programme écrit en Lisp) : ses solutions sont aléatoire dans le sens que la connaissance de N solutions ne donne strictement aucune information sur la solution N+1.

C'est inutilisable en pratique !!!! Mais d'un point de vue théorique c'est fort intéressant.

[GBo]

@Deedee, je me suis fait avoir par le titre aussi, fred3000gt pose en fait la question de savoir si les décimales de Pi peuvent servir de séquence PN.

[GBo]

Après qques recherches sur www, je serais tenté de répondre NON à la question ainsi refomulée car il apparait qu'il n'est toujours pas prouvé que Pi est "normal", "normal" au sens de :
https://en.wikipedia.org/wiki/Normal_number
cdlt,
GBo

[Deedee81]

je me suis fait avoir par le titre aussi, fred3000gt pose en fait la question de savoir si les décimales de Pi peuvent servir de séquence PN.

J'avais vu ça comme une sous-questions

[polo974]

un générateur doit pouvoir générer, si possible facilement et rapidement, mais avec les décimales de pi, on atteint très vite des limites pratiques, chaque digit étant nettement plus coûteux que le précédent.

alors qu'un LFSR (par exemple) n'augmente pas le coût à chaque coup. par contre, si on dispose d'une séquence de la longueur de LFSR et de son schéma, c'est foutu...

[Deedee81]

L'idéal reste le masque jetable . Je me demande s'il est encore utilisé (il l'était par le téléphone rouge mais je ne sais pas s'il est encore utilisé)

(EDIT je veux dire que là le coût éventuel de génération "vraiment" aléatoire n'est pas grave mais on sait aussi ses inconvénients)

[pm42]

L'idéal reste le masque jetable . Je me demande s'il est encore utilisé (il l'était par le téléphone rouge mais je ne sais pas s'il est encore utilisé)

Il est mathématiquement sur mais il pose d'autres problèmes : il faut le transmettre à son destinataire et être sur qu'une copie n'est pas faite au passage.
Parce que si c'est le cas, l'intercepteur décode absolument tout sans que ce soit détectable.
Et vu qu'on ne doit pas le réutiliser et qu'il doit être de même taille que la somme des messages transmis, la logistique est très lourde.

[Deedee81]

C'est bien à ces inconvénients là que je pensais

Mais je me demandais s'il était encore utilisé (pour le téléphone rouge, pour le transfert des clefs ils utilisaient la valide diplomatique).

[pm42]

C'est bien à ces inconvénients là que je pensais

Oui, j'ai raté la fin de ta phrase. Désolé.

Mais je me demandais s'il était encore utilisé (pour le téléphone rouge, pour le transfert des clefs ils utilisaient la valide diplomatique).

Il y a un commentaire intéressant ici sur sa réapparition dans le cadre du cryptage quantique. Et qui met en avant des inconvénients en usage normal que j'avais oubliés : pas de garantie d'intégrité ni d'authentification.

https://crypto.stackexchange.com/que...-used-or-can-b

[GBo]

un générateur doit pouvoir générer, si possible facilement et rapidement, mais avec les décimales de pi, on atteint très vite des limites pratiques, chaque digit étant nettement plus coûteux que le précédent. [...]

J'y avais pensé mais il y a la solution des digits déjà calculés par la communauté et à mettre en mémoire comme expliqué et essayé ici:
Using Pi digits to Generate Random Numbers: A Visual and Statistical Analysis
http://worldcomp-proceedings.com/proc/p2015/CSC2676.pdf
Comme dit plus haut on oublie pour la crypto puisque ça ne peut pas servir de masque jetable, mais ça peut servir quand même pour d'autres choses.

[fred3000gt]

Merci pour toutes les reponses....
Pour préciser ma question sans doute mal posée, j’ai cru comprendre qu’il n’y avait pas de generateur infini et non périodique, c’est vrai?
Or PI (ses decimales) me semble etre precisement infini et non periodique, vrai ou pas?
(Je ne m’intéresse pas à la qualité de ce générateur, c’est une question purement théorique)

[polo974]

sauf erreur racine de 2 aussi,
et puis e,
et puis ...

[pm42]

Pour préciser ma question sans doute mal posée, j’ai cru comprendre qu’il n’y avait pas de generateur infini et non périodique, c’est vrai?

Oui. Un ordinateur est un système fini.

Or PI (ses decimales) me semble etre precisement infini et non periodique, vrai ou pas?

Oui mais pas aléatoire. Et de toute manière, un ordinateur ne pas généré toutes les décimales : il est forcément limité à un moment.
L'infini est un concept mathématique très puissant mais dès qu'on arrive sur de la pratique, de la physique, on est en dans le fini : l'Univers accessible peut stocker une quantité d'information finie (probablement), a une quantité d'énergie finie, un temps pendant lequel on peut faire des calculs finis.

[invite36041331]

Bonjour,

L'idéal reste le masque jetable .

Le seul système cryptographie prouvé impossible à craquer*.

* : dans la mesure où la clef aléatoire (le masque) n a pas de biais.

Bonne journée.

[Garion]

l'Univers accessible peut stocker une quantité d'information finie (probablement), a une quantité d'énergie finie, un temps pendant lequel on peut faire des calculs finis.

Avec trois particules, je suis capable de stocker n'importe quelle information de n'importe quelle taille.
Il suffit que la fraction entre la distance AB et la distance BC me donne le résultat (sous forme d'un codage interprétable).
Donc le "probablement" ne me semble pas pertinent.

[pm42]

Avec trois particules, je suis capable de stocker n'importe quelle information de n'importe quelle taille.
Il suffit que la fraction entre la distance AB et la distance BC me donne le résultat (sous forme d'un codage interprétable).

Je veux bien que tu nous expliques comment comment tu réussis à mettre 3 particules aux distances en question avec précision et à les y maintenir.
Parce que tu vas vite tomber sur des problèmes comme l'agitation thermique, le principe d'incertitude, la distance de Planck, l'expansion de l'Univers...

C'est pour ça que je parlais de "pratique", pas de "j'ai imaginé un truc qui marche si l'Univers est newtonien, non quantique et statique".

[fred3000gt]

Oui. Un ordinateur est un système fini.


Oui mais pas aléatoire. Et de toute manière, un ordinateur ne pas généré toutes les décimales : il est forcément limité à un moment.
L'infini est un concept mathématique très puissant mais dès qu'on arrive sur de la pratique, de la physique, on est en dans le fini : l'Univers accessible peut stocker une quantité d'information finie (probablement), a une quantité d'énergie finie, un temps pendant lequel on peut faire des calculs finis.

On parle bien entendu de pseudoaléatoire

Ma question est purement théorique: PI est-il un exemple de générateur pseudoaléatoire infini et non-périodique?
peu importe que l'univers soit fini, ou que la facture électrique pour le calcul soit élevée

sauf erreur racine de 2 aussi,
et puis e,
et puis ...

Absolument d'accord, PI était juste un exemple, tout nombre irrationnel semble un bon candidat.

[polo974]

Avec trois particules, je suis capable de stocker n'importe quelle information de n'importe quelle taille.
Il suffit que la fraction entre la distance AB et la distance BC me donne le résultat (sous forme d'un codage interprétable).
Donc le "probablement" ne me semble pas pertinent.

Bon, là, tu as stocké (enfin, tu penses avoir) UNE information, reste juste à faire pareil avec une infinité d'info... Oups, l'univers est fini, on va manqué de particules avant la fin...

[GBo]

On parle bien entendu de pseudoaléatoire
Ma question est purement théorique: PI est-il un exemple de générateur pseudoaléatoire infini et non-périodique?
peu importe que l'univers soit fini, ou que la facture électrique pour le calcul soit élevée

Déjà Pi est un nombre irrationnel, ça c'est sûr, en voici la preuve mathématique la plus simple (datant de 1946):
https://www.ams.org/journals/bull/19...47-08821-2.pdf

Mais je ne sais pas s'il a été prouvé qu'un irrationnel ne pouvait pas contenir de périodicité dans la suite de décimale à partir d'un moment, avec la définition suivante de la périodicité:
"A decimal is called periodic if there are whole numbers N >= 0 and k > 0 such that for every n > N, d(n+k) = d(n).
This is the situation with numbers like 47/66, whose decimal expansion is 0.712121212121...
In this case, N = 1 and k = 2, so for all n > 1, d(n+2) = d(n).
There is a string of k digits in a row such that all the digits from the Nth on are gotten by writing down infinitely many copies of that single string."
Source: http://mathforum.org/library/drmath/view/53915.html

A noter que la non-périodicité de Pi (si elle est prouvée, ce qui j'ignore à cette heure), n'est pas un gage de normalité (cf. mon post #7), laquelle est aussi nécessaire pour une bonne séquence PN (Pseudo Noise) utilisable dans les sciences de l'ingénieur (ex. simu Monte Carlo).

cdlt,
GBo

[pm42]

Mais je ne sais pas s'il a été prouvé qu'un irrationnel ne pouvait pas contenir de périodicité dans la suite de décimale à partir d'un moment, avec la définition suivante de la périodicité:

Je ne suis pas sur de t'avoir compris à 100% parce que je ne suis pas encore bien réveillé mais si le développement est périodique à un moment, c'est un rationnel non ? La propriété de périodicité est réciproque (https://fr.wikipedia.org/wiki/Nombre_rationnel)

A noter que la non-périodicité de Pi (si elle est prouvée, ce qui j'ignore à cette heure), n

Elle découle de la propriété précédente.

[GBo]

Un exemple de non-périodique anormal (le 0 sort beaucoup plus souvent !):
0.1020030004000050000060000007 000000080000000090000000001000 00000000110000000000012...

[GBo]

Je ne suis pas sur de t'avoir compris à 100% parce que je ne suis pas encore bien réveillé mais si le développement est périodique à un moment, c'est un rationnel non ? La propriété de périodicité est réciproque (https://fr.wikipedia.org/wiki/Nombre_rationnel)
Elle découle de la propriété précédente.

Oui je me doutais d'un truc du genre mais moi non plus je n'étais pas bien réveillé (en plus ne pas être fortiche en maths, le drame de ma vie ).
D'accord donc, merci pm42.

[GBo]

Donc si j'en crois :

Is Pi Normal?
https://pi2e.ch/blog/2016/10/27/is-pi-normal/
qui pointe sur :
Digit Statistics of the First 22.4 Trillion Decimal Digits of Pi
https://arxiv.org/abs/1612.00489v1

J'en retiens que :
- Pi est irrationnel (donc non-périodique) : prouvé mathématiquement
- Pi est transcendant : prouvé mathématiquement
- Pi est normal : constaté expérimentalement sur un calcul énorme (fini) mais toujours pas prouvé mathématiquement

cdlt,
GBo

[pm42]

- Pi est irrationnel (donc non-périodique) : prouvé mathématiquement
- Pi est transcendant : prouvé mathématiquement
- Pi est normal : constaté expérimentalement sur un calcul énorme (fini) mais toujours pas prouvé mathématiquement

Pour les 2 1er, oui. Pour le 3ème, c'est ce que mes souvenirs d'études de maths me donnent et je ne crois pas qu'on ait trouvé la preuve depuis.

[GBo]

Par contre si je crée mon propre générateur en introduisant 0123456789 entre chaque décimale de Pi, je reste "normal" au niveau expérimental mais il y a des répétitions du même motif, sans être périodique au sens défini au dessus !
-> Pas très bon pour un PN, donc les critères ci-dessus ne suffisent peut-être pas à faire un bon PN ?

[pm42]

-> Pas très bon pour un PN

Je ne sais pas.