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 dcimaux aprs la virgule de PI. Ce fichier,
qui a t constitu partir d'un fichier ralis 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
prcdent tous les 500 blocs. Chaque bloc de 10 chiffres reprsente
deux nombres entiers composs de 5 chiffres allant de 0 99.999.

Dans l'application du test universel pour nombres pseudoalatoires:
http://cid-ebc6873e64120dfd.office.live.com/self.aspx/Cryptographie/Test%20=
Universel.pdf,
nous avons mis en caractres gras dans le fichier susmentionn
certains nombres particuliers. Etant donn que le nombre d'entiers,
composs de 5 chiffres dcimaux, 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 reprsent 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 probabilits donnes par la loi de
Poisson suivant la formule 100.000/(2.71828 * i!). Dans le cas
prsent, 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
prsents 8 fois, ce sont les nombres entiers 64.133 et 64.216. Vous
trouverez ces deux nombres entiers 8 fois en caractres 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 mentionns. Ce petit exemple concret
montre la ralit de fait d'un des aspects du test virtuel.

Emile
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