Clefs n°70 mars 2020
Clefs n°70 mars 2020
  • Prix facial : gratuit

  • Parution : n°70 de mars 2020

  • Périodicité : annuel

  • Editeur : CEA

  • Format : (230 x 280) mm

  • Nombre de pages : 52

  • Taille du fichier PDF : 7,8 Mo

  • Dans ce numéro : sacrées mathématiques !

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 38 - 39  |  Aller à la page   OK
Pages suivantes >
38 39
I LES DOMAINES D’APPLICATION PHYSIQUE DES PARTICULES « Les améliorations algorithmiques ont permis de réduire le temps nécessaire à la reconstruction des jets. Sans ces améliorations, l’analyse des données serait bien plus laborieuse. » [2] Matteo Cacciari, Gavin P.Salam, Dispelling the N^3 myth for the kt jet-finder, Phys.Lett. B641 (2006) 57-61 (inspirehep.net/record/700668) [3] www.cgal.org [4] Matteo Cacciari, Gavin P.Salam, Gregory Soyez, FastJet User Manual, Eur. Phys.J. C72 (2012) 1896 (inspirehep.net/record/955176) Contexte mathématique et algorithmique La reconstruction des jets est très complexe d’un point de vue algorithmique. Supposons qu’on ait N particules à recombiner en jets. Naïvement, le calcul de la distance minimale nécessite O(N 2) opérations. Cette étape est répétée O(N) fois pour passer de N particules à un nombre fini de jets, résultant en un algorithme de complexité O(N 3). Il est possible de réduire cela à une complexité d’ordre N log N. Comment ? D’abord en réalisant [2] que, pour identifier la distance minimale entre deux particules, il suffit d’identifier les plus proches voisins (PPV) au sens géométrique, c’est-à-dire en utilisant uniquement 2 2 2 la partie géométrique euclidienne ΔR = Δy ij + Δϕ ij. Grâce à ce résultat, on peut ensuite obtenir un algorithme O(N 2)  : on calcule d’abord le PPV de chaque particule (O(N 2) ). À chaque étape de la reconstruction, identifier le dij minimum parmi les PPV et recalculer les PPV des particules pour lesquelles le PPV a potentiellement changé sont tous deux d’ordre N. En répétant cette étape O(N) fois, on a un algorithme d’ordre N 2. Cet algorithme peut être mis en œuvre de manière efficace, par exemple en répartissant les particules en cellules sur une grille rectangulaire et en limitant la recherche des PPV aux cellules voisines. Un algorithme N log N La recherche des PPV peut encore être améliorée pour atteindre une complexité O(N log N) [2]. L’idée est de construire le diagramme de Voronoi associé aux particules  : pour un ensemble de points en deux dimensions (ici y et ϕ), on construit les bissectrices de chaque paire de points. Ces bissectrices s’intersectent et délimitent des cellules autour de chaque point (Fig. 1). L’ensemble de ces cellules (et leurs côtés) constitue le diagramme de Voronoi. La propriété mathématique qui nous intéresse est le fait que le PPV d’une particule est l’un des points appartenant à une des cellules voisines (Fig. 2). En moyenne, le nombre de cellules voisines d’une cellule donnée est d’ordre log(N). Ce qui réduit la recherche du PPV d’une particule à une opération d’ordre log(N). Qui plus est, il existe des algorithmes numériques (par exemple, disponibles dans la librairie CGAL [3]) qui permettent de construire le diagramme de Voronoi en O(N log(N)) - réduisant la phase d’initialisation de N 2 à N log(N) - et de retirer ou ajouter de nouveaux points en un temps O(1) - garantissant que chaque itération soit d’ordre log(N). Au total, ceci résulte en un algorithme N log(N). Ce type d’algorithme a été mis en œuvre sous la forme d’un programme appelé FastJet [4]. Les améliorations algorithmiques ont permis de réduire le temps nécessaire à la reconstruction des jets de 2-3 secondes par collision à 2-3 millisecondes pour N3000 (typique au LHC). Sans ces améliorations, il serait impossible de reconstruire les jets lors du processus de sélection des événements au LHC et l’analyse des données elle-même serait bien plus laborieuse. Fig. 1  : construction du diagramme de Voronoi  : Le programme FastJet  : www.fastjet.fr les bissectrices des segments reliant le point 0 et les Fig. 2  : le plus proche voisin du point dans la cellule rouge est à autres points définissent une cellule autour du point 0. chercher dans les cellules voisines (en bleu). 38 - Sacrées mathématiques ! 1 4 0 2 3 3 2 1 0 -1 -2 -3 a -3 -2 -1 0 1 2 3 Les voix de la recherche - #70 - Clefs
Quand Alice rencontre Bob Pour y parvenir, il fallait mathématiser les notions d’information, de traitement de l’information et de complexité de ces traitements. Devenue mathématique, la cryptographie va alors donner des applications à des théories abstraites, comme la théorie des groupes ou celle des corps finis. Un exemple ? Choisissons un nombre premier p et un nombre 2 ≤ g ≤ p-2, g devant satisfaire quelques propriétés supplémentaires [1]  : étant donné un nombre 1 ≤ a ≤ p-2 quelconque, on peut facilement calculer x=g a modp, où moddésigne le reste de la division euclidienne, y compris lorsque les nombres a, g et p sont très grands. Le problème inverse, qui demande de trouver a étant donnés g, p et x, est par contre très complexe et on ne connait pas aujourd’hui d’algorithmes capables de le résoudre rapidement sur un ordinateur, en tout cas non quantique. Donc, si on choisit des nombres suffisamment grands, révéler g, p et x ne révèle pas a - à moins d’accepter de faire des calculs pendant plusieurs milliards d’années ! Mais comment Alice et Bob, les stars de la cryptographie moderne, utilisent-ils cette complexité TECHNOLOGIES DE L’INFORMATION La cryptographie, science de la protection de l’information, est une discipline à la frontière de l’informatique et des mathématiques. Confinée pendant plusieurs siècles aux domaines diplomatique et militaire, elle est longtemps restée artisanale et ce n’est qu’à partir des années cinquante qu’elle s’est dotée de bases théoriques solides. pour communiquer secrètement ? C’est simple. D’abord, ils se mettent d’accord sur g et p, qui ne sont pas secrets. Alice tire ensuite au hasard 1 ≤ a ≤ p-2 et envoie x=g a modp à Bob qui fait de même en tirant au hasard 1 ≤ b ≤ p-2 et renvoie y=g b modp à Alice. Le tour de magie résulte dans le fait qu’Alice et Bob peuvent alors respectivement calculer y a modp=(g b modp) a modp=g ba modp=s et x b modp=(g a modp) b modp=g ab modp=s et obtenir le même résultats, un secret commun qu’ils utiliseront pour garder leurs communications confidentielles. Eve, la traditionnelle espionne de l’histoire, a écouté leurs échanges mais elle ne connait que g, p, x et y. Or, à moins qu’elle ne patiente quelques milliards d’années, x et y ne révèlent respectivement ni a ni b. Impossible donc pour Eve de retrouver s et de percer les secrets d’Alice et de Bob. Ce protocole, bien que très simple, est au cœur de la sécurité des échanges sur Internet. Mais l’histoire ne s’arrête pas là… La recherche en cryptographie reste toujours très active avec notamment le développement de nouvelles méthodes pour calculer directement sur des données chiffrées ou encore résister aux ordinateurs quantiques. LES DOMAINES D’APPLICATION PAR RENAUD SIRDEY (Direction de la recherche technologique) Renaud Sirdey est directeur de recherche au Laboratoire confiance des systèmes logiciels (Département des systèmes et circuits intégrés numériques). [1] En termes techniques, g doit être un générateur du groupe multiplicatif Z*p. Clefs - #70 - Les voix de la recherche Sacrées mathématiques ! - 39



Autres parutions de ce magazine  voir tous les numéros


Liens vers cette page
Couverture seule :


Couverture avec texte parution au-dessus :


Couverture avec texte parution en dessous :