Bonjour et bienvenue ! Dans cette vidéo, nous allons parler d’une méthode toute simple pour créer un générateur minimaliste de nombres qui ont l’air aléatoires, en nous basant sur les propriétés de la suite de Fibonacci. Mais d’abord, qu’est-ce qu’un PRNG ? C’est l’acronyme anglais pour Pseudo-Random Number Generator, ce qui veut dire en français « Générateur de Nombres Pseudo-Aléatoires ». Comme le nom l’indique, c’est un algorithme qui génère une séquence de nombres qui ont l’air aléatoires. Cela veut dire que les nombres consécutifs n’ont pas l’air d’être corrélés. Cependant, un examen minutieux de la séquence peut révéler l’algorithme utilisé et donc permettra de prédire les futures valeurs. Cette classe d’algorithmes n’est pas destinée à être purement et parfaitement aléatoire, ou « complètement imprévisible ». Il faut en effet un autre genre de système pour produire des nombres totalement imprévisibles, qui sont essentiels pour les applications de sécurité par exemple. Au contraire, un PRNG est totalement déterministe. Cela veut dire qu’une séquence peut être reproduite en connaissant l’état complet de l’algorithme. C’est une propriété très demandée par beaucoup de disciplines scientifiques et technologiques, comme les simulations de phénomènes physiques ou la transmission de données par exemple. Idealement, plus l’algorithme a un grand état interne (c’est à dire qu’il mémorise plus de bits), plus il va traiter d’informations, plus la séquence générée ressemblera à une vraie séquence aléatoire, et plus la séquence sera longue, donc mettra plus de temps pour reboucler. En théorie, chaque bit ajouté à l’état interne devrait doubler la longueur de la séquence générée. Vous allez vous demander : Pourquoi cette vidéo est-elle si importante ? Après tout, les algorithmes de PRNG sont déjà bien connus, très étudiés, et largement répandus. Les bricolages des années 1950 sont déjà bien loin. La découverte du générateur présenté dans cette vidéo vient de recherches sur les algorithmes de checksum, qui sont des systèmes où la vitesse, la simplicité et la compacité sont essentielles. Découvrir un générateur vraiment minimaliste est donc une bonne nouvelle, pour créer des checksums plus efficaces mais aussi tous plein d'autres algorithmes dérivés. Plus intéressant peut-être, cela remet en question la croyance que les PRNG nécessitent forcément une multiplication, une division ou toute forme de nombre premier. Voyons maintenant les principes de systèmes existants. De nos jours, l’un des PRNG les plus utilisés est le LFSR, ou « Linear Feedback Shift Register. » C'est un Registre à Décalage à Rétroaction Linéaire. C’est le générateur préféré pour les systèmes compacts car ils n’ont souvent besoin que de quelques portes logiques en plus de cellules mémoires. Ces portes logiques, mathématiquement, réalisent ce qu’on appelle la multiplication d’un polynôme binaire par un polynôme générateur, ce qui est l’équivalent d’un nombre premier pour des polynomes de corps finis. Merci Évariste Galois ! Une autre famille bien connue de PRNG, l’une des premières d’ailleurs, s’appelle Générateurs Congruentiels Linéaires, ou LCG en anglais. Ceux-cis consistent simplement à multiplier et additionner un nombre par des constantes dites « magiques », qui sont souvent soit des nombres premiers soit des nombres qui ont été sélectionnés pour leurs propriétés et leur comportement. Par rapport à l’addition, la multiplication et la division sont considérées comme « chères », car ces opérations prennent plus de temps et de circuits électroniques que l’addition. Cela augmente les coûts et réduit les performances, donc on aimerait bien s’en passer. Nous allons donc voir comment aucun de ces ingrédients lourds ou délicats n’est requis pour la méthode présentée dans cette vidéo. Intéressons-nous maintenant à la suite de Fibonacci, cet algorithme ridiculement célèbre alors qu’il consiste simplement à additionner les deux nombres précédents. Cela crée une séquence exponentielle dont le taux de croissance est appelé le nombre d’Or, ou Phi, un nombre transcendental qui vaut 1,6 suivi d’une infinité de décimales dont nous n’avons que faire. Le nombre d’or est montré dans la colonne de droite, où l’on voit la convergence du rapport entre les deux nombres consécutifs. Sur le diagramme X-Y, on voit aussi que Phi est visible comme la pente formée par l’asymptote de tous les points. Maintenant, voici la première astuce. Puisqu’un nombre transcendental contient une suite infinie de décimales qui ne se répètent pas, l’émergence d’une constante transcendentale à partir d’une simple série d’additions fait espérer que seule l’addition serait nécessaire à la création d’une suite pseudo-aléatoire. Si c’était le cas, des générations de mathématiciens auraient dû s’en apercevoir depuis bien longtemps et ce serait une méthode standard aujourd’hui. Wikipedia mentionne bien des algorithmes qui s’inspirent de la suite de Fibonacci mais ne l’utilisent pas directement. Par exemple, Marsaglia a créé une famille d’algorithmes appelés « lagged » Fibonacci, ou « Fibonacci à retard », destinés aux périodes ridiculement longues, au moyen de dizaines de variables. Mais pour certaines applications, comme les nôtres, nous avons besoin du minimum de variables possible. Alors où est le problème ? Il y a 250 ans, la séquence de Fibonacci était déjà étudiée en arithmétique modulaire, c’est à dire : modulo un nombre entier. En d’autres termes, chaque opération tronque le résultat lorsque celui-ci dépase le « module ». On appelle la séquence ainsi créée, la « séquence de Pisano », car Fibonacci venait de Pise. Les propriétés de ces séquences sont très bien connues et nous allons maintenant l’étudier avec le modulo 16, car l’informatique adore les puissances de deux. Une des propriétés qui nous intéresse est que lorsque le module est une puissance de deux, la longueur de la séquence de Pisano générée est une fois et demi la valeur du module. Ainsi, modulo 16, la séquence reboucle au bout de 24 pas, comme le montre l’algorithme. Le diagramme X-Y semble relativement diffus, mais le nombre de points est ridiculement petit. Conclusion : Les séquences de Pisano ne peuvent être utilisées en pratique car le résultat serait très mauvais ou inefficace. Cependant, d’autres propriétés sont intéressantes et nous sommes très près de corriger le défaut. Intéressons-nous maintenant à la façon dont les ordinateurs additionnent les nombres. Les nombres entiers sont habituellement représentés par des mots de 8, 16, 32 ou 64 bits, et pour les additionner, nous avons besoin d'un circuit appelé un additionneur. Oui je voulais faire une blague sur la vipère noire mais elle ne fonctionne qu’en anglais. Voilà. Vous vous doutez bien que ce circuit accepte deux opérandes, X et Y, et fournit la somme en sortie. Ensuite, les mathématiciens l’oublient souvent, mais un additionneur binaire fournit aussi une entrée de retenue (carry-in) et une sortie de retenue (carry-out). Ah, vous les voyez bien là ? Dans un ordinateur, on en dispose gratuitement et ils vont nous sauver la mise même s’ils sont généralement ignorés. Mettons-les donc au travail. Nous allons maintenant voir ce qu’on appelle le "End Around Carry", soit en français : « faire passer la retenue de l’autre côté ». C’est une vieille technique utilisée par certains des premiers ordinateurs, afin de gérer un format de données binaires oublié depuis déjà bien longtemps. C’est vraiment simple : lorsqu’une retenue est générée, le bit de retenue est réinjecté dans le bit de poids faible du résultat, soit par une autre addition, soit par un incrémenteur dédié. Lorsque plusieurs additions doivent être chaînées, l’astuce consiste à utiliser explicitement le signal de retenue pour le réinjecter dans l’entrée suivante, afin d’économiser la latence d’un incrémenteur dédié dans le chemin de données. Maintenant que la retenue est distincte, elle fait alors explicitement partie de l’état du système. C’est une différence, subtile mais importante, par rapport à une opération de modulo classique. Vous voyez probablement où cela nous mène : cette astuce résoud le problème posé par la séquence de Pisano classique. Et maintenant, nous pouvons mettre ensemble tous ces éléments pour former l’algorithme PEAC : Pisano + End Around Carry. Je trouve que c’est un peu plus explicite que le nom donné par Marsaglia qui était « add-with-carry generators » Nous savons déjà que les séquences de Pisano sont ridiculement courtes. Une façon de voir PEAC est que pour rallonger la séquence, elle doit être perturbée afin de mieux couvrir tous les états possibles. On peut faire cela facilement, avec l’addition modifiée que nous venons de voir : contrairement à l’algorithme de Pisano, la retenue n’est plus ignorée, mais réinjectée dans le bit de poids faible. Ainsi, chaque fois que la somme dépasse la valeur limite, le prochain résultat sera augmenté de 1. De loin, on pourrait penser que cela est équivalent à un modulo N-1, tel que l’utilise l’algorithme de Fletcher, mais la retenue est maintenant un élément individuel, séparé, ce qui en fait un système modulo n+1 ! Et justement, dans cet exemple avec n = 16, la largeur X est aussi égale à 16 mais la hauteur Y est maintenant égale à 16 + 1 = 17 car cela représente la valeur précédente (X) augmentée de la retenue. On voit que le résultat pour n = 16 est très bon : la séquence boucle après 135 itérations au lieu de seulement 24. Au passage, une séquence qui reboucle est appelée ici une "orbite". Pour un modulo N donné, la longueur de l’orbite n’est plus une fois et demie N, mais la moitié du carré de N, ce qui est considérablement meilleur. On voit aussi que l’orbite couvre la moitié de la surface de façon bien homogène. L’autre moitié de la surface est couverte par une autre orbite complémentaire, comme le montre la symétrie des carrés blancs et noirs. Donc avec ce système, et de par sa nature, toutes les orbites vont maintenant par paire. Mais ce n’est pas tout ! Comparé aux autres types de circuits, ce comportement est créé par un seul additionneur, dont on a rebouclé la retenue. Seuls les LFSR ont un circuit équivalent plus simple mais cet avantage disparaît dans une réalisation logicielle et les LFSR ont des inconvénients que PEAC n’a pas. Mais ce sera discuté une autre fois. L’exemple de N = 16 correspond à une largeur de 4 bits, on l’appelle w4 pour faire plus simple. Cet exemple n’est utile que pour illustrer l’idée et il est intéressant de tester d’autres largeurs pour envisager des applications pratiques. La vidéo qui suit montre l’espace d’états de tous les PEAC, d’une largeur de 1 à 16. Chaque couleur représente une orbite, quand cela est possible. La visualisation à plusieurs échelles permet de juger de la qualité des différents générateurs. Par exemple si on distingue des lignes ou des formes, la séquence générée risque d’avoir l’air moins aléatoire. En pratique, nous désirons l’orbite la plus longue, ce qui revient à n’avoir que deux orbites. Nous allons donc chercher les images qui ne contiennent que du bleu et du vert. C’est le cas pour les largeurs de 2, 3, 4, 10 et 16 bits. Les autres largeurs ont plus d’orbites, souvent avec des longueurs inégales, donc à éviter. La durée de calcul quadruple chaque fois que la largeur augmente de 1, ce qui rend les grandes largeurs très difficiles à évaluer. Par exemple, la largeur w26 est un candidat très probable qui n’a pas encore pu être validé car cela nécessite 2^52 itérations ! Mais surtout, le plus pertinent est de déterminer la structure de w32 puisque c’est une taille très courante en informatique. Si la largeur 32 a suffisamment peu d’orbites, alors l’algorithme correspondant pourra générer deux fois plus de données par cycle, comparé à w16. Ce serait un gain de performance très important. Cependant, prouver cela nécessite de calculer plus de 16 milliards de milliards d’itérations, ce qui est impossible en temps raisonnable sur un ordinateur de bureau. Cela requiert donc de meilleurs algorithmes et une puissance de calcul considérablement plus élevée. (musique) A ce stade, vous devriez avoir compris comment transformer la suite de Fibonacci en un générateur de nombres pseudo-aléatoires, au moyen d’une petite astuce de programmation. Il n’y a aucun « nombre magique » à choisir, aucune opération complexe ni théorie absconse. Le seul inconvénient est que seules certaines tailles donnent des résultats appropriés. La recherche de nouvelles tailles valides continue. Pour les tailles déjà validées, l’algorithme PEAC peut être réalisé par un circuit électronique très rapide, limité seulement à la vitesse de l’additionneur. En logiciel, sans optimiser pour une plateforme donnée, générer un nouveau nombre ne prend que 4 instructions de base, dont la moitié peut être exécutées en parallèle. Bien sûr, comme tous les autres algorithmes de cette catégorie, les séquences ont des propriétés qui les rendent impropres à une utilisation directe en cryptographie. Ne l’utilisez donc pas pour votre casino ! D’un autre côté, PEAC est une base très prometteuse pour créer d’autres algorithmes, en particulier des checksums. C’est le candidat idéal pour remplacer ou améliorer l’algorithme de Fletcher ou Adler. Dans certains cas, PEAC pourrait aussi remplacer les CRC basés sur les LFSR. L'histoire complète de cet algorithme est bien plus complexe que la présentation rapide de cette petite vidéo. J’ai conservé les détails et résultats qui sont pertinents à la création de nouveaux checksums, car la génération de séquences pseudo-aléatoires extrêmement longues est une science déjà bien établie. Si vous voulez en savoir plus, revenez voir les prochaines vidéos de cette chaine et suivez le projet sur Hackaday.io. Je travaille actuellement à valider w26 et w32, et améliorer la théorie qui les décrit. Comme toujours, un grand merci à toutes les personnes qui, directement ou indirectement, ont contribué à cette vidéo. En différé de Paris, c’était Yann au micro.