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.

    Hasard et mathématiques. © Futura 
    Hasard et mathématiques. © Futura 

    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. 

    Acheter le livre 


    Cliquez pour acheter le livre 

    À découvrir également : L'univers des codes secrets de l'Antiquité à Internet paru en 2012 chez Ixelles.