Je vous fais une petite mise en contexte. Lors d'une séance de tp de C, nous devions entre autre générer une clé de 256 bit de façon "aléatoire".
Nous avions l'implémentation des données fourni, la voici :
uint_8 key[32];
Pour faire la génération je faisais donc ça
/* Cast explicité pour plus de clarté */
key = (uint_8) rand();
Lorsque le prof a vu, il m'a donné une astuce que "les experts en C connaissent" et a ajouté ceci
key = (uint_8) (rand() >> 8);
Il m'a dit que c'est pour éliminer des bit parasites (pas sûr qu'il avait employé ce terme). Il a ajouté que c'était en rapport
au fonctionnement du rand() qui utilise un générateur à congruence linéaire et que ce procédé induit à une certaine périodicité des bit
sur les nombres généré consécutivement (enfin je crois...). J'aimerai bien en savoir plus à propos de ça, est ce que quelqu'un aurait une explication ?
Le >>8 veut dire qu'on décale le nombre vers la droite de 8 bits. Dans le contexte actuel, tu aurais pu diviser par 256 et ça doonnerait la même chose. rand() ne donne pas une fonction parfaitement uniforme. Si tu veux le tester, obtiens une première valeur et conserve la. Ensuite appelle rand() jusqu'à ce que tu retrouves ce nombre. Compte en même temps le nombre d'itérations. Tu verras que le compte est rarement le même.
Je pense que la limite pour rand() est 32768. Diviser par 256 risque de donner pire encore à mon avis.
- Edité par PierrotLeFou 18 novembre 2022 à 19:14:37
Le Tout est souvent plus grand que la somme de ses parties.
rand() est une fonction de la libc, la bibliothèque standard de C. Cette fonction devrait renvoyer un nombre pseudo-aléatoire compris entre 0 et RAND_MAX. Il n'y a aucunes contraintes de «qualité», la seule contrainte est que RAND_MAX doit au moins être égal à 32767.
Quand on consulte le standard, on trouve comme remarque :
There are no guarantees as to the quality of the random sequence produced and some implementations
are known to produce sequences with distressingly non-random low-order bits. Applications with
particular requirements should use a generator that is known to be sufficient for their needs.
Il est notoire (du moins à l'époque de l'édition de C11) que certaines implémentations donne des npa peu «aléatoires» sur les bit de faibles poids. Une technique consiste donc à simplement les ignorer. Un RAND_MAX à 32767 indique plus ou moins implicitement sur les architectures modernes que les npa sont générés sur au moins 16bits. Comme il ne t'en faut que 8, tu peux récupérer les bits de poids plus fort avec un décalage, le fameux >>8. Ici ça va fonctionner relativement bien car par contrainte, les npa ne seront pas négatif, car les décalages à droite sur des entiers signés négatifs dépend de l'implémentation.
PierrotLeFou a écrit:
Le >>8 veut dire qu'on décale le nombre vers la droite de 8 bits. Dans le contexte actuel, tu aurais pu diviser par 256 et ça doonnerait la même chose. rand() ne donne pas une fonction parfaitement uniforme. Si tu veux le tester, obtiens une première valeur et conserve la. Ensuite appelle rand() jusqu'à ce que tu retrouves ce nombre. Compte en même temps le nombre d'itérations. Tu verras que le compte est rarement le même.
Je pense que la limite pour rand() est 32768. Diviser par 256 risque de donner pire encore à mon avis.
- Edité par PierrotLeFou il y a environ 1 heure
Attention ce test n'est pas concluant. Un générateur de nombres aléatoires peut très bien (et finira par) produire 8 fois de suite le nombre 8. En revanche un générateur de nombres pseudo-aléatoires aura forcément un cycle.
Le >>8 veut dire qu'on décale le nombre vers la droite de 8 bits. Dans le contexte actuel, tu aurais pu diviser par 256 et ça doonnerait la même chose. rand() ne donne pas une fonction parfaitement uniforme. Si tu veux le tester, obtiens une première valeur et conserve la. Ensuite appelle rand() jusqu'à ce que tu retrouves ce nombre. Compte en même temps le nombre d'itérations. Tu verras que le compte est rarement le même.
Je pense que la limite pour rand() est 32768. Diviser par 256 risque de donner pire encore à mon avis.
- Edité par PierrotLeFou il y a environ 1 heure
Je ne comprends pas pourquoi 256 pourrait donner un mauvais résultat. Est-ce une histoire d'arrondi identique après avoir effectué la division par 256 sur des rand() consécutif ou autre chose ?
Aussi, que signifie l'acronyme npa et à quoi est dû le fait qu'il y ait des "npa peu «aléatoires» sur les bit de faibles poids" ?
- Edité par ValentinBarrau1 18 novembre 2022 à 21:34:24
Il y a plusieurs types de générateurs de nombres pseudo aléatoires, la qualité des nombres produits est très variables. En général, plus un générateur est rapide et plus la qualité est faible.
Mais bon, tu n'as pas besoin d'un générateur de qualité cryptographique pour un TP je suppose ^_^.
rand() est une fonction de la libc, la bibliothèque standard de C. Cette fonction devrait renvoyer un nombre pseudo-aléatoire compris entre 0 et RAND_MAX. Il n'y a aucunes contraintes de «qualité», la seule contrainte est que RAND_MAX doit au moins être égal à 32767.
Quand on consulte le standard, on trouve comme remarque :
There are no guarantees as to the quality of the random sequence produced and some implementations
are known to produce sequences with distressingly non-random low-order bits. Applications with
particular requirements should use a generator that is known to be sufficient for their needs.
Il est notoire (du moins à l'époque de l'édition de C11) que certaines implémentations donne des npa peu «aléatoires» sur les bit de faibles poids. Une technique consiste donc à simplement les ignorer. Un RAND_MAX à 32767 indique plus ou moins implicitement sur les architectures modernes que les npa sont générés sur au moins 16bits. Comme il ne t'en faut que 8, tu peux récupérer les bits de poids plus fort avec un décalage, le fameux >>8. Ici ça va fonctionner relativement bien car par contrainte, les npa ne seront pas négatif, car les décalages à droite sur des entiers signés négatifs dépend de l'implémentation.
Que signifie l'acronyme npa ? Aussi, à quoi est dû le fait qu'il y ait des "npa peu «aléatoires» sur les bit de faibles poids" ?
La fonction suivante est parfaitement cyclique d'un cycle de 65536, mais je ne sais pas si elle est uniforme ... Peut-être en remplaçant 75 par un autre multiplicateur? - #include <stdio.h> #include <time.h> int rand2(int n) { static int s; if(n == 0) { s = s * 75 % 65537; return s-1; } s = n % 65537; } int main(void) { rand2(time(NULL)); int d = rand2(0); int c = 1; while(rand2(0) != d) c++; printf("%d\n", c); }
Le Tout est souvent plus grand que la somme de ses parties.
rand() est censé donner un nombre équiprobable entre 0 et RAND_MAX-1.
RAND_MAX c'est souvent 32768 (toujours vu ça), ou alors j'imagine une autre puissance de 2 supérieure (jamais vu mais bon)
Mathématiquement, dans la mesure ou 32768 se divise par 256, alors prendre rand()%256 doit donner également un nombre équiprobable entre 0 et 255.
On dit qu'il faut éviter les modulos : oui si le nombre que tu choisis ne divise par RAND_MAX : il y aura alors une probabilité un peu plus forte sur les petits nombres.
Un exemple extrême :
rand()%32000 (je veux un nombre entre 0 et 31999). (considérons RAND_MAX a 32768)
Tu vois bien que le 0,1,2,...,767 ont deux fois plus de chances de tomber que les nombres 768... 31999
(car 0 tombera pour rand()=0 et rand()=32000, 1 tombera pour rand()=1 et rand()=32001, etc...)
Mais si on nombre N dans rand()%N divise RAND_MAX, alors la chaque nombre sera équiprobable.
rand() est censé donner un nombre équiprobable entre 0 et RAND_MAX-1.
RAND_MAX c'est souvent 32768 (toujours vu ça), ou alors j'imagine une autre puissance de 2 supérieure (jamais vu mais bon)
[…]
-
Edité par Fvirtman il y a 9 minutes
Il n'y a aucune contrainte particulière sur rand imposée par le standard. La valeur 32767 est une valeur minimum imposée par le standard, qui est prise au pied de la lettre par microsoft. D'autres libc (comme gnu libc sous linux64) peuvent choisir d'autres valeurs, (2147483647 par exemple).
C'est pas forcément l'OS, c'est surtout l'implémentation de la libc qui détermine la valeur.
[QUESTION] bit "parasites" rand()
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html