Table of Contents
Introduction : L’importance des générateurs de nombres aléatoires
La génération de nombres aléatoires est l’un des piliers fondamentaux de l’informatique moderne. Que ce soit pour les simulations scientifiques, les jeux vidéo, la cryptographie ou l’apprentissage automatique, la qualité des nombres aléatoires générés peut faire la différence entre un système fiable et un système défaillant.
PRNG vs TRNG : Comprendre la différence
Il existe deux grandes catégories de générateurs de nombres aléatoires :
Les générateurs de nombres véritablement aléatoires (TRNG - True Random Number Generators) s’appuient sur des phénomènes physiques imprévisibles comme le bruit thermique, la désintégration radioactive ou les fluctuations atmosphériques. Ces générateurs produisent une entropie réelle mais sont généralement lents et nécessitent du matériel spécialisé.
Les générateurs de nombres pseudo-aléatoires (PRNG - Pseudo-Random Number Generators) utilisent des algorithmes déterministes pour produire des séquences qui semblent aléatoires. Initialisés avec une graine (seed), ils produisent toujours la même séquence pour une graine donnée. Cette propriété, qui peut sembler être une faiblesse, est en réalité précieuse pour la reproductibilité des expériences scientifiques.
Critères de qualité d’un PRNG
Un bon générateur pseudo-aléatoire doit satisfaire plusieurs critères :
- Période longue : Le nombre de valeurs générées avant que la séquence ne se répète
- Distribution uniforme : Chaque valeur possible doit avoir la même probabilité d’apparition
- Indépendance statistique : Aucune corrélation ne doit exister entre les valeurs successives
- Performance : La génération doit être rapide pour les applications à haut débit
- Portabilité : Le même code doit produire les mêmes résultats sur différentes plateformes
Dans cet article, nous allons explorer en profondeur les générateurs disponibles en C, des fonctions standard jusqu’aux algorithmes modernes comme XORshift et PCG.
Les fonctions standard : rand() et srand()
Utilisation basique
La bibliothèque standard C fournit les fonctions rand() et srand() pour la génération de nombres pseudo-aléatoires :
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void) {
// Initialisation de la graine avec l'heure actuelle
srand((unsigned int)time(NULL));
// Génération de 10 nombres aléatoires
for (int i = 0; i < 10; i++) {
int random_value = rand();
printf("Valeur %d: %d\n", i + 1, random_value);
}
// Génération dans une plage [0, max]
int max = 100;
int random_in_range = rand() % (max + 1);
printf("Nombre entre 0 et %d: %d\n", max, random_in_range);
return 0;
}Le problème du seeding avec time()
L’utilisation de time(NULL) comme graine présente plusieurs problèmes :
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void) {
// PROBLÈME 1: Résolution d'une seconde seulement
// Si le programme est lancé plusieurs fois dans la même seconde,
// il produira la même séquence
time_t seed = time(NULL);
printf("Graine: %ld\n", (long)seed);
// PROBLÈME 2: Prévisibilité
// Un attaquant connaissant l'heure approximative de lancement
// peut réduire considérablement l'espace de recherche
// SOLUTION: Combiner plusieurs sources d'entropie
unsigned int better_seed = (unsigned int)(
time(NULL) ^
(clock() << 16) ^
((unsigned int)&seed) // Adresse en mémoire (ASLR)
);
srand(better_seed);
printf("Meilleure graine: %u\n", better_seed);
return 0;
}Limitations critiques de rand()
La fonction rand() souffre de plusieurs limitations majeures :
#include <stdio.h>
#include <stdlib.h>
// LIMITATION 1: Période courte
// Sur de nombreuses implémentations, la période est de 2^31 ou moins
// C'est insuffisant pour les simulations Monte Carlo modernes
// LIMITATION 2: Bits de poids faible de mauvaise qualité
void demonstrate_low_bit_problem(void) {
srand(12345);
printf("Parité des 20 premiers nombres (rand() %% 2):\n");
for (int i = 0; i < 20; i++) {
// Les bits de poids faible peuvent montrer des patterns
printf("%d ", rand() % 2);
}
printf("\n");
// SOLUTION: Utiliser les bits de poids fort
printf("Meilleure méthode (rand() > RAND_MAX/2):\n");
srand(12345);
for (int i = 0; i < 20; i++) {
printf("%d ", rand() > RAND_MAX / 2 ? 1 : 0);
}
printf("\n");
}
// LIMITATION 3: Le biais du modulo
void demonstrate_modulo_bias(void) {
// Si RAND_MAX = 32767 et on veut un nombre entre 0 et 999
// 32767 % 1000 = 767
// Les nombres 0-767 ont une probabilité légèrement plus élevée
int range = 1000;
int count[1000] = {0};
srand(42);
for (int i = 0; i < 1000000; i++) {
count[rand() % range]++;
}
// Vérification du biais
int expected = 1000000 / range;
printf("Attendu: ~%d par valeur\n", expected);
printf("0: %d, 500: %d, 999: %d\n", count[0], count[500], count[999]);
}
// SOLUTION: Rejet du biais
int unbiased_random_range(int max) {
int threshold = RAND_MAX - (RAND_MAX % max);
int r;
do {
r = rand();
} while (r >= threshold);
return r % max;
}
int main(void) {
demonstrate_low_bit_problem();
printf("\n");
demonstrate_modulo_bias();
return 0;
}XORshift : Algorithme rapide et élégant
Principe mathématique
L’algorithme XORshift, développé par George Marsaglia en 2003, repose sur une observation mathématique élégante : certaines séquences d’opérations XOR et de décalages de bits peuvent produire des séquences avec une période maximale.
Le principe fondamental est le suivant :
x = x XOR (x << a)
x = x XOR (x >> b)
x = x XOR (x << c)Où les constantes a, b, c sont soigneusement choisies pour garantir une période maximale de 2^n - 1 (n étant le nombre de bits de l’état).
XORshift32 : La version basique
#include <stdint.h>
#include <stdio.h>
// XORshift32 - Période: 2^32 - 1
typedef struct {
uint32_t state;
} xorshift32_t;
void xorshift32_seed(xorshift32_t* rng, uint32_t seed) {
// La graine ne doit jamais être 0
rng->state = seed ? seed : 1;
}
uint32_t xorshift32_next(xorshift32_t* rng) {
uint32_t x = rng->state;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
rng->state = x;
return x;
}
// Génération d'un flottant dans [0, 1)
float xorshift32_float(xorshift32_t* rng) {
return (xorshift32_next(rng) >> 8) * (1.0f / 16777216.0f);
}
int main(void) {
xorshift32_t rng;
xorshift32_seed(&rng, 12345);
printf("XORshift32 - 10 premiers nombres:\n");
for (int i = 0; i < 10; i++) {
printf("%u\n", xorshift32_next(&rng));
}
printf("\nFlottants dans [0, 1):\n");
for (int i = 0; i < 5; i++) {
printf("%.6f\n", xorshift32_float(&rng));
}
return 0;
}XORshift64 : Pour les systèmes 64 bits
#include <stdint.h>
#include <stdio.h>
// XORshift64 - Période: 2^64 - 1
typedef struct {
uint64_t state;
} xorshift64_t;
void xorshift64_seed(xorshift64_t* rng, uint64_t seed) {
rng->state = seed ? seed : 1;
}
uint64_t xorshift64_next(xorshift64_t* rng) {
uint64_t x = rng->state;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
rng->state = x;
return x;
}
// Génération d'un double dans [0, 1)
double xorshift64_double(xorshift64_t* rng) {
return (xorshift64_next(rng) >> 11) * (1.0 / 9007199254740992.0);
}
// Génération dans une plage [min, max]
int64_t xorshift64_range(xorshift64_t* rng, int64_t min, int64_t max) {
uint64_t range = (uint64_t)(max - min + 1);
uint64_t threshold = -range % range; // Élimination du biais
uint64_t r;
do {
r = xorshift64_next(rng);
} while (r < threshold);
return min + (int64_t)(r % range);
}
int main(void) {
xorshift64_t rng;
xorshift64_seed(&rng, 88172645463325252ULL);
printf("XORshift64 - 10 premiers nombres:\n");
for (int i = 0; i < 10; i++) {
printf("%llu\n", (unsigned long long)xorshift64_next(&rng));
}
printf("\nNombres dans [1, 100]:\n");
xorshift64_seed(&rng, 88172645463325252ULL);
for (int i = 0; i < 10; i++) {
printf("%lld\n", (long long)xorshift64_range(&rng, 1, 100));
}
return 0;
}XORshift128 : L’équilibre parfait
#include <stdint.h>
#include <stdio.h>
// XORshift128 - Période: 2^128 - 1
typedef struct {
uint32_t x, y, z, w;
} xorshift128_t;
void xorshift128_seed(xorshift128_t* rng, uint32_t seed) {
// Initialisation de Splitmix pour disperser la graine
uint64_t s = seed;
s = (s ^ (s >> 30)) * 0xBF58476D1CE4E5B9ULL;
rng->x = (uint32_t)(s >> 32);
rng->y = (uint32_t)s;
s = (s ^ (s >> 27)) * 0x94D049BB133111EBULL;
rng->z = (uint32_t)(s >> 32);
rng->w = (uint32_t)s;
// S'assurer qu'au moins un état n'est pas 0
if (rng->x == 0 && rng->y == 0 && rng->z == 0 && rng->w == 0) {
rng->x = 1;
}
}
uint32_t xorshift128_next(xorshift128_t* rng) {
uint32_t t = rng->x;
t ^= t << 11;
t ^= t >> 8;
rng->x = rng->y;
rng->y = rng->z;
rng->z = rng->w;
rng->w ^= rng->w >> 19;
rng->w ^= t;
return rng->w;
}
// Fonction de saut - avance de 2^64 états
void xorshift128_jump(xorshift128_t* rng) {
static const uint32_t JUMP[] = {
0x8764000b, 0xf542d2d3, 0x6fa035c3, 0x77f2db5b
};
uint32_t x = 0, y = 0, z = 0, w = 0;
for (int i = 0; i < 4; i++) {
for (int b = 0; b < 32; b++) {
if (JUMP[i] & (1U << b)) {
x ^= rng->x;
y ^= rng->y;
z ^= rng->z;
w ^= rng->w;
}
xorshift128_next(rng);
}
}
rng->x = x;
rng->y = y;
rng->z = z;
rng->w = w;
}
int main(void) {
xorshift128_t rng;
xorshift128_seed(&rng, 42);
printf("XORshift128 - 10 premiers nombres:\n");
for (int i = 0; i < 10; i++) {
printf("%u\n", xorshift128_next(&rng));
}
printf("\nAprès un saut de 2^64 états:\n");
xorshift128_jump(&rng);
for (int i = 0; i < 5; i++) {
printf("%u\n", xorshift128_next(&rng));
}
return 0;
}Avantages de XORshift
- Extrêmement rapide : Seulement quelques opérations XOR et décalages
- Simple à implémenter : Peu de lignes de code
- Portable : Pas de dépendances matérielles
- Bonne distribution : Passe la plupart des tests statistiques de base
PCG (Permuted Congruential Generator)
Principe et avantages
Le générateur PCG, développé par Melissa O’Neill en 2014, combine les avantages des générateurs linéaires congruentiels (LCG) avec une fonction de sortie non linéaire pour améliorer la qualité statistique.
L’idée clé est de séparer :
- L’état interne : Un LCG simple mais avec une très longue période
- La fonction de sortie : Une permutation qui améliore la qualité des bits
Implémentation complète de PCG32
#include <stdint.h>
#include <stdio.h>
// Structure PCG32
typedef struct {
uint64_t state;
uint64_t inc;
} pcg32_t;
// Initialisation avec deux graines
void pcg32_seed(pcg32_t* rng, uint64_t initstate, uint64_t initseq) {
rng->state = 0U;
rng->inc = (initseq << 1U) | 1U; // Doit être impair
pcg32_next(rng);
rng->state += initstate;
pcg32_next(rng);
}
// Génération du prochain nombre
uint32_t pcg32_next(pcg32_t* rng) {
uint64_t oldstate = rng->state;
// Avancer l'état LCG
rng->state = oldstate * 6364136223846793005ULL + rng->inc;
// Calculer la fonction de sortie (XSH RR)
// XSH = XOR Shift High
// RR = Random Rotation
uint32_t xorshifted = (uint32_t)(((oldstate >> 18U) ^ oldstate) >> 27U);
uint32_t rot = oldstate >> 59U;
return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}
// Génération dans une plage [0, bound)
uint32_t pcg32_bounded(pcg32_t* rng, uint32_t bound) {
// Élimination du biais modulo avec la méthode de Lemire
uint32_t threshold = -bound % bound;
for (;;) {
uint32_t r = pcg32_next(rng);
if (r >= threshold) {
return r % bound;
}
}
}
// Génération d'un flottant dans [0, 1)
float pcg32_float(pcg32_t* rng) {
return ldexpf((float)pcg32_next(rng), -32);
}
// Génération d'un double dans [0, 1)
double pcg32_double(pcg32_t* rng) {
uint32_t a = pcg32_next(rng) >> 5; // 27 bits
uint32_t b = pcg32_next(rng) >> 6; // 26 bits
return (a * 67108864.0 + b) * (1.0 / 9007199254740992.0);
}
int main(void) {
pcg32_t rng;
pcg32_seed(&rng, 42, 54);
printf("PCG32 - 10 premiers nombres:\n");
for (int i = 0; i < 10; i++) {
printf("%u\n", pcg32_next(&rng));
}
printf("\nNombres dans [0, 6) (simulation d'un dé):\n");
pcg32_seed(&rng, 42, 54);
for (int i = 0; i < 20; i++) {
printf("%u ", pcg32_bounded(&rng, 6) + 1);
}
printf("\n");
printf("\nFlottants:\n");
for (int i = 0; i < 5; i++) {
printf("%.10f\n", pcg32_double(&rng));
}
return 0;
}Flux multiples avec PCG
Une caractéristique unique de PCG est le support de flux (streams) multiples :
#include <stdint.h>
#include <stdio.h>
typedef struct {
uint64_t state;
uint64_t inc;
} pcg32_t;
void pcg32_seed(pcg32_t* rng, uint64_t initstate, uint64_t initseq);
uint32_t pcg32_next(pcg32_t* rng);
// Créer des flux indépendants pour le parallélisme
void demonstrate_streams(void) {
pcg32_t rng1, rng2, rng3;
// Même état initial, flux différents
pcg32_seed(&rng1, 42, 1); // Flux 1
pcg32_seed(&rng2, 42, 2); // Flux 2
pcg32_seed(&rng3, 42, 3); // Flux 3
printf("Trois flux indépendants avec la même graine:\n");
printf("Flux 1\tFlux 2\tFlux 3\n");
printf("------\t------\t------\n");
for (int i = 0; i < 5; i++) {
printf("%u\t%u\t%u\n",
pcg32_next(&rng1),
pcg32_next(&rng2),
pcg32_next(&rng3));
}
}
// Fonction de saut - avance de 2^64 états
void pcg32_advance(pcg32_t* rng, uint64_t delta) {
uint64_t cur_mult = 6364136223846793005ULL;
uint64_t cur_plus = rng->inc;
uint64_t acc_mult = 1;
uint64_t acc_plus = 0;
while (delta > 0) {
if (delta & 1) {
acc_mult *= cur_mult;
acc_plus = acc_plus * cur_mult + cur_plus;
}
cur_plus = (cur_mult + 1) * cur_plus;
cur_mult *= cur_mult;
delta >>= 1;
}
rng->state = acc_mult * rng->state + acc_plus;
}
int main(void) {
demonstrate_streams();
return 0;
}Autres algorithmes notables
Mersenne Twister (MT19937)
Le Mersenne Twister est l’un des PRNG les plus utilisés, notamment comme générateur par défaut dans de nombreux langages de programmation.
#include <stdint.h>
#include <stdio.h>
#define MT_N 624
#define MT_M 397
#define MT_MATRIX_A 0x9908b0dfUL
#define MT_UPPER_MASK 0x80000000UL
#define MT_LOWER_MASK 0x7fffffffUL
typedef struct {
uint32_t mt[MT_N];
int mti;
} mt19937_t;
void mt19937_seed(mt19937_t* rng, uint32_t seed) {
rng->mt[0] = seed;
for (rng->mti = 1; rng->mti < MT_N; rng->mti++) {
rng->mt[rng->mti] =
(1812433253UL * (rng->mt[rng->mti - 1] ^
(rng->mt[rng->mti - 1] >> 30)) + rng->mti);
}
}
uint32_t mt19937_next(mt19937_t* rng) {
uint32_t y;
static const uint32_t mag01[2] = {0x0UL, MT_MATRIX_A};
if (rng->mti >= MT_N) {
int kk;
for (kk = 0; kk < MT_N - MT_M; kk++) {
y = (rng->mt[kk] & MT_UPPER_MASK) | (rng->mt[kk + 1] & MT_LOWER_MASK);
rng->mt[kk] = rng->mt[kk + MT_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
}
for (; kk < MT_N - 1; kk++) {
y = (rng->mt[kk] & MT_UPPER_MASK) | (rng->mt[kk + 1] & MT_LOWER_MASK);
rng->mt[kk] = rng->mt[kk + (MT_M - MT_N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
}
y = (rng->mt[MT_N - 1] & MT_UPPER_MASK) | (rng->mt[0] & MT_LOWER_MASK);
rng->mt[MT_N - 1] = rng->mt[MT_M - 1] ^ (y >> 1) ^ mag01[y & 0x1UL];
rng->mti = 0;
}
y = rng->mt[rng->mti++];
// Tempering
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
return y;
}
int main(void) {
mt19937_t rng;
mt19937_seed(&rng, 5489);
printf("Mersenne Twister - 10 premiers nombres:\n");
for (int i = 0; i < 10; i++) {
printf("%u\n", mt19937_next(&rng));
}
return 0;
}LFSR (Linear Feedback Shift Register)
#include <stdint.h>
#include <stdio.h>
// LFSR 32 bits avec polynôme x^32 + x^22 + x^2 + x + 1
typedef struct {
uint32_t state;
} lfsr32_t;
void lfsr32_seed(lfsr32_t* rng, uint32_t seed) {
rng->state = seed ? seed : 1;
}
uint32_t lfsr32_next(lfsr32_t* rng) {
// Tap positions: 32, 22, 2, 1
uint32_t bit = ((rng->state >> 0) ^
(rng->state >> 10) ^
(rng->state >> 30) ^
(rng->state >> 31)) & 1U;
rng->state = (rng->state >> 1) | (bit << 31);
return rng->state;
}
// Version Galois LFSR (plus rapide)
uint32_t lfsr32_galois_next(lfsr32_t* rng) {
uint32_t lsb = rng->state & 1U;
rng->state >>= 1;
if (lsb) {
rng->state ^= 0x80200003U; // Polynôme de rétroaction
}
return rng->state;
}
int main(void) {
lfsr32_t rng;
lfsr32_seed(&rng, 0xACE1u);
printf("LFSR32 - 10 premiers nombres:\n");
for (int i = 0; i < 10; i++) {
printf("0x%08X\n", lfsr32_next(&rng));
}
return 0;
}Comparaison des performances
#include <stdint.h>
#include <stdio.h>
#include <time.h>
#define ITERATIONS 100000000
// Prototypes des générateurs (définitions omises pour la concision)
uint32_t xorshift32_next(void* rng);
uint32_t xorshift128_next(void* rng);
uint32_t pcg32_next(void* rng);
uint32_t mt19937_next(void* rng);
void benchmark(const char* name, uint32_t (*generator)(void*), void* rng) {
clock_t start = clock();
uint32_t sum = 0;
for (int i = 0; i < ITERATIONS; i++) {
sum += generator(rng);
}
clock_t end = clock();
double seconds = (double)(end - start) / CLOCKS_PER_SEC;
double mops = ITERATIONS / seconds / 1000000.0;
printf("%-15s: %.2f sec, %.2f M ops/sec (checksum: %u)\n",
name, seconds, mops, sum);
}
// Résultats typiques sur un CPU moderne:
// XORshift32 : 0.08 sec, 1250.0 M ops/sec
// XORshift128 : 0.12 sec, 833.3 M ops/sec
// PCG32 : 0.15 sec, 666.7 M ops/sec
// Mersenne Twister: 0.45 sec, 222.2 M ops/sec
// rand() stdlib : 0.50 sec, 200.0 M ops/secCas d’usage pratiques
Simulations Monte Carlo
Les simulations Monte Carlo nécessitent des générateurs avec une période très longue et une excellente distribution :
#include <stdint.h>
#include <stdio.h>
#include <math.h>
// Estimation de Pi par Monte Carlo
double estimate_pi(pcg32_t* rng, int iterations) {
int inside_circle = 0;
for (int i = 0; i < iterations; i++) {
// Points aléatoires dans [0, 1) x [0, 1)
double x = pcg32_double(rng);
double y = pcg32_double(rng);
// Vérifier si le point est dans le quart de cercle
if (x * x + y * y < 1.0) {
inside_circle++;
}
}
// Pi/4 = aire du quart de cercle / aire du carré
return 4.0 * inside_circle / iterations;
}
// Intégration Monte Carlo
double monte_carlo_integrate(pcg32_t* rng,
double (*f)(double),
double a, double b,
int samples) {
double sum = 0.0;
for (int i = 0; i < samples; i++) {
double x = a + (b - a) * pcg32_double(rng);
sum += f(x);
}
return (b - a) * sum / samples;
}
double test_function(double x) {
return sin(x) * sin(x); // Intégrale sur [0, Pi] = Pi/2
}
int main(void) {
pcg32_t rng;
pcg32_seed(&rng, 12345, 67890);
printf("Estimation de Pi:\n");
printf(" 1,000 itérations: %.6f\n", estimate_pi(&rng, 1000));
printf(" 100,000 itérations: %.6f\n", estimate_pi(&rng, 100000));
printf(" 10,000,000 itérations: %.6f\n", estimate_pi(&rng, 10000000));
printf(" Valeur réelle: %.6f\n", M_PI);
printf("\nIntégration de sin²(x) sur [0, Pi]:\n");
pcg32_seed(&rng, 12345, 67890);
printf(" Résultat Monte Carlo: %.6f\n",
monte_carlo_integrate(&rng, test_function, 0, M_PI, 1000000));
printf(" Valeur exacte: %.6f\n", M_PI / 2);
return 0;
}Jeux vidéo
Pour les jeux vidéo, on a besoin de reproductibilité (pour les replays) et de rapidité :
#include <stdint.h>
#include <stdio.h>
typedef struct {
xorshift128_t rng;
uint32_t initial_seed;
} game_random_t;
// Initialisation avec la graine du niveau
void game_random_init(game_random_t* gr, uint32_t level_seed) {
gr->initial_seed = level_seed;
xorshift128_seed(&gr->rng, level_seed);
}
// Réinitialisation pour replay
void game_random_reset(game_random_t* gr) {
xorshift128_seed(&gr->rng, gr->initial_seed);
}
// Drop d'item avec probabilité
typedef enum {
ITEM_NONE,
ITEM_COMMON,
ITEM_RARE,
ITEM_EPIC,
ITEM_LEGENDARY
} item_rarity_t;
item_rarity_t random_item_drop(game_random_t* gr) {
uint32_t roll = xorshift128_next(&gr->rng) % 10000;
if (roll < 1) return ITEM_LEGENDARY; // 0.01%
if (roll < 10) return ITEM_EPIC; // 0.09%
if (roll < 100) return ITEM_RARE; // 0.9%
if (roll < 2000) return ITEM_COMMON; // 19%
return ITEM_NONE; // 80%
}
// Dégâts avec variance
int random_damage(game_random_t* gr, int base_damage, float variance) {
float multiplier = 1.0f + (xorshift128_float(&gr->rng) * 2.0f - 1.0f) * variance;
return (int)(base_damage * multiplier);
}
// Position aléatoire de spawn
typedef struct { float x, y; } vec2_t;
vec2_t random_spawn_position(game_random_t* gr, float min_x, float max_x,
float min_y, float max_y) {
vec2_t pos;
pos.x = min_x + xorshift128_float(&gr->rng) * (max_x - min_x);
pos.y = min_y + xorshift128_float(&gr->rng) * (max_y - min_y);
return pos;
}Avertissement : Cryptographie
ATTENTION : N’utilisez JAMAIS ces PRNG pour la cryptographie !
#include <stdio.h>
/*
* AVERTISSEMENT CRITIQUE
* =====================
*
* Les générateurs présentés dans cet article (XORshift, PCG, MT)
* ne sont PAS cryptographiquement sûrs !
*
* Problèmes de sécurité :
* - État interne récupérable à partir de quelques sorties
* - Prédictibilité de la séquence future
* - Pas de résistance aux attaques par analyse
*
* Pour la cryptographie, utilisez :
* - Linux: getrandom() ou /dev/urandom
* - Windows: BCryptGenRandom() ou CryptGenRandom()
* - OpenSSL: RAND_bytes()
* - Bibliothèques: libsodium, libcrypto
*/
// MAUVAIS - Ne jamais faire ça !
void bad_generate_password(void) {
pcg32_t rng;
pcg32_seed(&rng, time(NULL), 0); // Graine prévisible !
// Un attaquant peut deviner le mot de passe
char password[17];
for (int i = 0; i < 16; i++) {
password[i] = 'a' + pcg32_bounded(&rng, 26);
}
password[16] = '\0';
// NE PAS UTILISER !
}
// BON - Utilisez une source cryptographique
#include <sys/random.h>
void good_generate_password(void) {
char password[17];
unsigned char random_bytes[16];
// Utiliser une source d'entropie du système
if (getrandom(random_bytes, 16, 0) != 16) {
// Erreur - gérer proprement
return;
}
for (int i = 0; i < 16; i++) {
password[i] = 'a' + (random_bytes[i] % 26);
}
password[16] = '\0';
}Bonnes pratiques
1. Choisir le bon générateur pour l’application
/*
* Guide de sélection :
*
* | Application | Générateur recommandé |
* |---------------------------|----------------------|
* | Prototypage rapide | rand() stdlib |
* | Jeux vidéo | XORshift128 |
* | Simulations scientifiques | PCG32 ou MT19937 |
* | Parallélisme massif | PCG (avec streams) |
* | Cryptographie | CSPRNG système |
* | Embarqué/Contraint | XORshift32 ou LFSR |
*/2. Toujours initialiser correctement
#include <stdint.h>
#include <time.h>
#include <unistd.h>
// Fonction de seeding robuste
uint64_t get_robust_seed(void) {
uint64_t seed = 0;
// Combiner plusieurs sources d'entropie
seed ^= (uint64_t)time(NULL);
seed ^= (uint64_t)clock() << 32;
seed ^= (uint64_t)getpid() << 16;
// Mixer avec une fonction de hachage simple
seed = (seed ^ (seed >> 30)) * 0xBF58476D1CE4E5B9ULL;
seed = (seed ^ (seed >> 27)) * 0x94D049BB133111EBULL;
seed = seed ^ (seed >> 31);
return seed;
}
// Utilisation
void example_robust_init(void) {
pcg32_t rng;
uint64_t seed = get_robust_seed();
pcg32_seed(&rng, seed, seed >> 32);
}3. Éviter le biais de distribution
// MAUVAIS : biais modulo
int bad_dice(pcg32_t* rng) {
return 1 + pcg32_next(rng) % 6; // Biaisé !
}
// BON : rejet du biais
int good_dice(pcg32_t* rng) {
return 1 + pcg32_bounded(rng, 6); // Non biaisé
}
// BON : utiliser des flottants pour les petites plages
int good_dice_float(pcg32_t* rng) {
return 1 + (int)(pcg32_double(rng) * 6);
}4. Documenter la graine utilisée
// Pour la reproductibilité des expériences
void run_experiment(void) {
uint64_t seed = get_robust_seed();
// TOUJOURS logger la graine
printf("Experiment seed: 0x%016llX\n", (unsigned long long)seed);
pcg32_t rng;
pcg32_seed(&rng, seed, 0);
// ... expérience ...
}Pièges courants à éviter
1. Réinitialiser la graine trop souvent
// MAUVAIS : réinitialisation dans une boucle
void bad_random_loop(void) {
for (int i = 0; i < 1000; i++) {
srand(time(NULL)); // ERREUR ! Même graine pendant 1 seconde
int r = rand();
// Tous les appels dans la même seconde donnent le même nombre !
}
}
// BON : initialiser une seule fois
void good_random_loop(void) {
srand(time(NULL)); // Une seule fois au début
for (int i = 0; i < 1000; i++) {
int r = rand();
}
}2. Utiliser une graine de 0 sans précaution
// MAUVAIS : graine 0 pour XORshift donne toujours 0
void bad_xorshift_init(void) {
xorshift32_t rng;
rng.state = 0; // ERREUR !
// xorshift32_next(&rng) retournera toujours 0
}
// BON : vérifier et corriger la graine
void xorshift32_seed_safe(xorshift32_t* rng, uint32_t seed) {
rng->state = seed ? seed : 1; // Jamais 0
}3. Partager l’état entre threads sans protection
#include <pthread.h>
// MAUVAIS : état global partagé
xorshift128_t global_rng; // Data race !
void* bad_thread_func(void* arg) {
for (int i = 0; i < 1000; i++) {
xorshift128_next(&global_rng); // Race condition !
}
return NULL;
}
// BON : un générateur par thread
void* good_thread_func(void* arg) {
int thread_id = *(int*)arg;
pcg32_t local_rng;
pcg32_seed(&local_rng, 42, thread_id); // Stream unique par thread
for (int i = 0; i < 1000; i++) {
pcg32_next(&local_rng); // Pas de race condition
}
return NULL;
}4. Ignorer les bits de poids faible de rand()
// MAUVAIS avec certaines implémentations de rand()
int bad_coin_flip(void) {
return rand() % 2; // Peut alterner 0, 1, 0, 1, ...
}
// BON : utiliser les bits de poids fort
int good_coin_flip(void) {
return rand() > RAND_MAX / 2;
}
// MEILLEUR : utiliser un vrai générateur
int best_coin_flip(pcg32_t* rng) {
return pcg32_next(rng) & 1;
}5. Supposer que la période est infinie
/*
* Rappel des périodes :
* - rand() stdlib : souvent 2^31 (peut être atteint en quelques secondes)
* - XORshift32 : 2^32 - 1
* - XORshift128 : 2^128 - 1 (pratiquement infini)
* - PCG32 : 2^64 (avec 2^63 streams possibles)
* - Mersenne Twister : 2^19937 - 1
*
* Pour les simulations longues, choisissez un générateur avec
* une période bien supérieure au nombre d'appels prévus !
*/Conclusion
Les générateurs de nombres pseudo-aléatoires sont des outils fondamentaux en programmation C. Le choix du bon algorithme dépend de votre cas d’usage :
Tableau comparatif des algorithmes
| Algorithme | Période | État (octets) | Vitesse | Qualité | Usage recommandé |
|---|---|---|---|---|---|
| rand() | ~2^31 | 4 | Moyenne | Faible | Prototypage uniquement |
| XORshift32 | 2^32-1 | 4 | Excellente | Bonne | Embarqué, jeux simples |
| XORshift128 | 2^128-1 | 16 | Excellente | Très bonne | Jeux, simulations |
| PCG32 | 2^64 | 16 | Très bonne | Excellente | Usage général, parallélisme |
| Mersenne Twister | 2^19937-1 | 2500 | Bonne | Excellente | Simulations scientifiques |
| LFSR | 2^n-1 | n/8 | Excellente | Faible | Matériel, brouillage |
Points clés à retenir
- Ne jamais utiliser rand() pour des applications sérieuses - Sa qualité statistique est insuffisante
- XORshift est le meilleur compromis vitesse/qualité pour la plupart des applications
- PCG offre la meilleure combinaison de qualité, vitesse et fonctionnalités (streams)
- Mersenne Twister reste la référence pour les simulations scientifiques exigeantes
- Pour la cryptographie, utilisez TOUJOURS les fonctions du système (getrandom, /dev/urandom)
Ressources supplémentaires
- PCG: https://www.pcg-random.org/
- TestU01: Bibliothèque de tests statistiques pour PRNG
- Dieharder: Suite de tests de qualité aléatoire
- “The Art of Computer Programming, Vol. 2” de Donald Knuth
En maîtrisant ces générateurs, vous serez capable de choisir et d’implémenter la solution optimale pour vos besoins en génération de nombres aléatoires.
Advertisement
In-Article Ad
Dev Mode
Tags
Mahmoud DEVO
Senior Full-Stack Developer
I'm a passionate full-stack developer with 10+ years of experience building scalable web applications. I write about Vue.js, Node.js, PostgreSQL, and modern DevOps practices.
Enjoyed this article?
Subscribe to get more tech content delivered to your inbox.
Related Articles
📄c
10 min read
Enumerations en C : guide complet avec exemples pratiques et bonnes pratiques
Apprenez a utiliser les enumerations en C pour un code plus lisible et maintenable. Exemples pratiques, verification de plage et astuces.
Read article
📄c
12 min read
Bit-fields et tableaux en C : guide pratique pour optimiser la memoire
Maitrisez les bit-fields et tableaux en C. Apprenez a creer des structures compactes, acceder aux elements et iterer efficacement sur vos donnees.
Read article
📄c
12 min read
C : Typedef, stdint.h et Storage Classes pour gérer les types
Apprenez à utiliser typedef, les types fixes de stdint.h et les storage classes (auto, register, static, extern) en C pour améliorer la portabilité et la lisibilité de votre code.
Read article