Test universel pour nombres pseudoaléatoires

2 réponses
Avatar
Emile
Le fichier PI-DATA.pdf
http://cid-ebc6873e64120dfd.office.live.com/self.aspx/Cryptographie/PI-DATA=
.pdf
donne 500.000 chiffres d=E9cimaux apr=E8s la virgule de PI. Ce fichier,
qui a =E9t=E9 constitu=E9 =E0 partir d'un fichier r=E9alis=E9 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 =E9crit, en marge =E0 droite, le nombre de blocs qui
pr=E9c=E8dent tous les 500 blocs. Chaque bloc de 10 chiffres repr=E9sente
deux nombres entiers compos=E9s de 5 chiffres allant de 0 =E0 99.999.

Dans l'application du test universel pour nombres pseudoal=E9atoires:
http://cid-ebc6873e64120dfd.office.live.com/self.aspx/Cryptographie/Test%20=
Universel.pdf,
nous avons mis en caract=E8res gras dans le fichier susmentionn=E9
certains nombres particuliers. Etant donn=E9 que le nombre d'entiers,
compos=E9s de 5 chiffres d=E9cimaux, qui figurent dans le fichier est de
100.000 (=3D2*50.000), et que chaque entier est compris de 0 =E0 99.999,
la probabilit=E9 moyenne que chaque entier sera repr=E9sent=E9 dans le
fichier est de 1. En fait, chaque entier peut figurer 0,1, 2, 3, 4, 5,
6, 7, 8 (=3D i) fois suivant les probabilit=E9s donn=E9es par la loi de
Poisson suivant la formule 100.000/(2.71828 * i!). Dans le cas
pr=E9sent, le coefficient lambda est =E9gal =E0 1. Pour la valeur de i =3D =
8,
le probabilit=E9 est de 0.91... En fait, il y a 2 nombres qui sont
pr=E9sents 8 fois, ce sont les nombres entiers 64.133 et 64.216. Vous
trouverez ces deux nombres entiers 8 fois en caract=E8res gras dans le
fichier susmentionn=E9. 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 =E9galement mentionn=E9s. Ce petit exemple concret
montre la r=E9alit=E9 de fait d'un des aspects du test virtuel.

Emile

2 réponses

Avatar
Francois Grieu
Le 09/07/2010 16:33, Emile Musyck expose un:

test universel pour nombres pseudoaléatoires:


<http://cid-ebc6873e64120dfd.office.live.com/self.aspx/Cryptographie/Test%20Universel.pdf>

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
Avatar
xtof pernod
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:


<http://cid-ebc6873e64120dfd.office.live.com/self.aspx/Cryptographie/Test%20Universel.pdf>

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.