Test universel pour nombres pseudoaléatoires

Le
Emile
Le fichier PI-DATA.pdf
http://cid-ebc6873e64120dfd.office.live.com/self.aspx/Cryptographie/PI-DATA=
.pdf
donne 500.000 chiffres décimaux après la virgule de PI. Ce fichier,
qui a été constitué à partir d'un fichier réalisé avec le logic=
iel
Super-Pi, regroupe les chiffres par blocs de dix chiffres, cinq blocs
par ligne, et un interligne tous les vingt lignes. Il y a donc 50.000
blocs. IL est écrit, en marge à droite, le nombre de blocs qui
précèdent tous les 500 blocs. Chaque bloc de 10 chiffres représente
deux nombres entiers composés de 5 chiffres allant de 0 à 99.999.

Dans l'application du test universel pour nombres pseudoaléatoires:
http://cid-ebc6873e64120dfd.office.live.com/self.aspx/Cryptographie/Test%20=
Universel.pdf,
nous avons mis en caractères gras dans le fichier susmentionné
certains nombres particuliers. Etant donné que le nombre d'entiers,
composés de 5 chiffres décimaux, qui figurent dans le fichier est de
100.000 (=2*50.000), et que chaque entier est compris de 0 à 99.999,
la probabilité moyenne que chaque entier sera représenté dans le
fichier est de 1. En fait, chaque entier peut figurer 0,1, 2, 3, 4, 5,
6, 7, 8 (= i) fois suivant les probabilités données par la loi de
Poisson suivant la formule 100.000/(2.71828 * i!). Dans le cas
présent, le coefficient lambda est égal à 1. Pour la valeur de i = =
8,
le probabilité est de 0.91 En fait, il y a 2 nombres qui sont
présents 8 fois, ce sont les nombres entiers 64.133 et 64.216. Vous
trouverez ces deux nombres entiers 8 fois en caractères gras dans le
fichier susmentionné. Le nombre entier 00000 ne figure pas dans la
liste, mais bien les nombres 00001 (le plus petit) et 99.999 (le plus
grand) lesquels sont également mentionnés. Ce petit exemple concret
montre la réalité de fait d'un des aspects du test virtuel.

Emile
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Francois Grieu
Le #22343411
Le 09/07/2010 16:33, Emile Musyck expose un:

test universel pour nombres pseudoaléatoires:



Résumé et reformulation: il est proposé un "test universel"
pour l'évaluation d'un générateur d'entiers aléatoires.
Partant de N valeurs Xj consécutives:
- si nécessaire, re-normaliser les Xj en Yj, avec Yj un entier
dans [0..N-1] pour j dans [0..N-1], par multiplication par
une constante appropriée et troncature;
- compter le nombre d'occurences Nk de chacune des N valeurs
possibles de Yj = k, pour j dans [0..N-1], k dans [0..N-1];
note: Somme(Nk) = N
- compter le nombre d'occurences Mi de chacune des N+1 valeurs
possibles de Nk = i, pour k dans [0..N-1], i dans [0..N];
note: Somme(i*Mi) = N
- faire un test statistique selon la méthode du chi-deux sur
la distribution des Mi, qui devrait suivre en gros une
loi de Poisson de paramètre lambda=1 (pour de grands N, de
l'ordre de 10^5 ou plus)

Le test est appliqué
- avec N0000, aux groupes de 5 chiffres décimaux dans Pi;
- avec N0000, aux deux générateurs congruentiels linéaires
X := X*16807 MOD (2^31-1) avec Y = floor(X*N/(2^31-1))
X := X*65539 MOD 2^31 avec Y = floor(X*N/2^31)
- avec N1071, aux cryptogrammes produits par l'algorithme
SED-128 de l'auteur.
Selon l'auteur, le test détecte le premier générateur congruentiel
linéaire comme médiocre, et le second (RANDU) comme très mauvais,
ce qui est conforme à leur réputation; les deux autres générateurs
passent.

Encouragé par cela, l'auteur conjecture que passer le test suffit
à démontrer le caractère aléatoire d'une suite de nombres.



Je conteste la conjecture. Ce test échoue à éliminer des
générateurs pourtant éxécrables. Par exemple, si on part d'un
générateur de Xj aléatoires qui passe le test, que l'on groupe
les Xj par paires consécutives, et trie chaque paire, on obtient
un autre générateur qui passe le test (puisque son score est
essentiellement inchangé), mais qui est fort mauvais.

Par ailleurs, je crains que les résultats encourageants sur
les générateurs congruentiels linéaires soient assez dépendants
du N utilisé, du fait de la renormalisation.

Plus généralement, il est illusoire d'espérer un test universel,
surtout dans un contexte cryptographique. Au contraire, la
cryptographie permet de construire un générateur pseudoaléatoire,
muni d'une clé secrète, qui passe tout test non muni de la clé,
mais dont toute séquence suffisemment grande est distinguable
par un test approprié munis la clé.

Francois Grieu
xtof pernod
Le #22344531
Le 10/07/2010 08:19, Francois Grieu a fait rien qu'à écrire:
Le 09/07/2010 16:33, Emile Musyck expose un:
test universel pour nombres pseudoaléatoires:



Résumé et reformulation: il est proposé un "test universel"
pour l'évaluation d'un générateur d'entiers aléatoires.



C'est même plus que ça: la 1ere phrase stipule que ça porte sur l'
"évaluation du caractère aléatoire d’une série de nombres".

Si c'était uniquement sur des nombres produits par un algorithme
quelconque, ça a du sens: on peut très bien imaginer un test qui
"reconnaisse" de telles suites de nombres, avec un très bon taux
de réussite. Infaillible, même, pourquoi pas.

La preuve de son existence étant à la charge de l'auteur de
la conjecture, cela va sans dire.


Partant de N valeurs Xj consécutives:
(...)

Le test est appliqué
- avec N0000, aux groupes de 5 chiffres décimaux dans Pi;



Je suis pas persuadé du bien fondé de cette manip'..

Il n'y a pas tant que ça de faits établis sur Pi. Sa transcendance
et son irrationnalité n'aident en rien ici ; sa répartition est
du genre "aussi loin qu'on a été, il est normal dans toutes les bases"

Et il n'est en aucun cas aléatoire, vu sous l'angle de la complexité
algorithmique. Les plus geeks connaissent certainement ce bout de
programme illisible, de 4 lignes, qui produit la valeur /exacte/ de Pi.

(...)
Encouragé par cela, l'auteur conjecture que passer le test suffit
à démontrer le caractère aléatoire d'une suite de nombres.




Ah ! Ca serait vraiment bien que l'auteur précise si c'est une suite
de nombres, quelconques, arbitraires, aléatoires ou supposés tels,
ou issus d'un générateur. On saurait alors de quoi on parle.

Il y a aussi l'expression "aléatoire parfait" que je capte pas.

De l'aléatoire pas parfait, je me doute:
1, 1, 1, 1, 2.03e37, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...


Je conteste la conjecture. (...)

Francois Grieu




Merci pour la reformulation, en tout cas. Ca aide bien =)

--
christophe.
Publicité
Poster une réponse
Anonyme