« L’important ce n’est pas d’avoir raison, mais d’être compris » a dit Dominique de Villepin, un soir à la télé. Je ne suis pas diplomate, mais cet adage s’applique aussi parfaitement dans le domaine des sciences, et surtout des mathématiques et de ses applications, où la vérité absolue nous échappera toujours un peu (merci, Monsieur Gödel) et nos heuristiques comblent les lacunes. Avoir tort est inévitable quand on défriche un sujet totalement nouveau, la compréhension est alors indispensable pour compenser les petites erreurs ou zones d’ombre. Donc, ces derniers mois, je vous ai parlé en détail de checksums [1], de Galois et des corps finis [2] ou de générateurs de nombres pseudo-aléatoires [3] [4], ravivant avec succès une bien vieille série. Tout cela pour établir les bases du présent article, qui synthétise enfin PEAC : un générateur de séquences pseudo-aléatoires (PRNG), dérivé accidentel de la séquence de Fibonacci, aux propriétés fascinantes et aux applications très intéressantes.
Pour résumer, PEAC signifie « Pisano with End Around Carry », car il désigne justement une famille d’algorithmes réalisant une structure mathématique proche de la suite de Fibonacci [5], modulo un nombre entier, donc lié aux périodes de Pisano [6]. La différence avec ces dernières est que le modulo est calculé en « complément à un » [7], aussi appelé « End Around Carry », ce qui modifie profondément les propriétés des séquences.
Les algorithmes PEAC sont compacts, efficaces et flexibles, en matériel comme en logiciel, ce qui en fait des alternatives intéressantes aux LFSR, par exemple. PEAC trouve sa place dans les PRNG, les CRC/checksums, les brouilleurs, ainsi que beaucoup d‘applications où des générateurs de séquences fixes sont requis, comme le stockage et la transmission d’informations, ou bien le traitement des signaux.
Les quatre précédents articles [1] [2] [3] [4] contiennent des références supplémentaires et des explications...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première