Dans plusieurs branches des mathématiques, on utilise des suites aléatoires. L’ennui est qu’il est difficile d’en fabriquer de manière automatisée. On utilise alors des suites construites à partir d’un algorithme déterministe qui semble avoir toutes les propriétés des suites aléatoires. On parle de suites pseudo-aléatoires.
au sommaire
Pour choisir aléatoirement un nombre entre 0 et 1.024, une idée est de jouer dix fois à pile ou face. En notant 0 les piles et 1 les faces, nous obtenons un nombre à dix chiffres binairesbinaires, comme par exemple 1001011111 (que nous avons effectivement trouvé ainsi). En décimal, cela donne 1+2+4+8+16+64+512, soit 607. Bien entendu, si on joue onze fois à pile ou face, on obtient un nombre entre 0 et 2.048, etc.
Dans plusieurs domaines des mathématiques (simulation, calcul scientifique, cryptographie), on a besoin d'une grande quantité de nombres aléatoires donc de suite de tels nombres. La méthode que nous venons de proposer devient vite impraticable.
La création du pseudo-aléatoire
Il est plus économique d'utiliser une suite déterministe ayant les apparences d'une suite aléatoire. Voici une recette pour en fabriquer une, de nombres entre 0 et 2147483646. On prend un premier terme réellement au hasard, par exemple l'heure en nanosecondes, qu'on appelle le germegerme, disons 3248455607. On multiplie ce nombre par 16807 et on garde le reste du résultat dans la division par 2147483647. On obtient 1316629168. On recommence la même opération avec ce nouveau nombre et ainsi de suite : 914927888, 1210101096, 1498983382, 1283038317, etc. Cette suite ressemble à une suite aléatoire, elle passe tous les tests usuels de répartition des suites aléatoires mais elle est pourtant déterministe.
Utilisation
Quand l'important est d'utiliser une suite de nombres équirépartis sur un intervalle donné, le pseudo-aléatoire peut remplacer l'aléatoire sans problème. Quand l'important est que les termes de la suite soient imprévisibles, ce n'est pas le cas. Dans la première catégorie, on trouve les utilisations en simulation et en calcul numériquenumérique, dans la seconde, les utilisations en cryptographiecryptographie.
Hervé Lehning
En savoir plus sur Hervé Lehning
Normalien et agrégé de mathématiques, Hervé Lehning a enseigné sa discipline une bonne quarantaine d'années. Fou de cryptographie, membre de l'Association des réservistes du chiffre et de la sécurité de l'information, il a en particulier percé les secrets de la boîte à chiffrer d'Henri II.
- Son blog MATH'MONDE sur Futura
- Le dernier livre d'Hervé Lehning :
À découvrir également : L'univers des codes secrets de l'Antiquité à Internet paru en 2012 chez Ixelles.