Tutte Institute for Mathematics and Computing

Jeudi 30 novembre, 15:30-16:30, Salle 3195, Pavillon André-Aisenstadt

Dans cet exposé, tous les ensembles sont finis. Les permutations sur des ensembles finis sont utiles dans plusieurs domaines des mathématiques et de l'informatique. Une permutation sur un ensemble de mots substitue un mot à un autre mot de façon unique. En informatique, les mots sont encodés par des chaînes de bits. Pour les chaînes de N bits, il y a un total de (2^N)! permutations et beaucoup d'entre elles peuvent avoir des points fixes, certaines peuvent n'avoir qu'un cycle, etc. En cryptographie, nous désirons par exemple trouver des permutations ayant de longs cycles pour éviter certaines attaques exhaustives. Si nos permutations étaient pigées au hasard équiprobablement parmi les (2^N)! permutations, alors il faudrait en moyenne N*(2^N)+(constante) bits aléatoires à manipuler/transformer pour générer une telle permutation. Une telle quantité de bits est gigantesque en général et les cryptographes tentent de contourner par toutes sortes d'astuces ce problème de mémoire. Une autre propriété, que nous appelons PM, plus difficile à saisir, est directement reliée à des notions de calcul différentiel sur des ensembles finis, voire des structures algébriques finies, mais pour cela il faudra venir m'écouter. Est-il possible pour tout entier positif N de construire un ensemble, disons A, de permutations sur les mots de N bits ayant un seul cycle, ne prenant que O(N) bits à décrire si lesdites permutations étaient pigées au hasard dans A et satisfaisant cette Propriété Mystérieuse très importante en cryptographie? Oui... pour N impair, et après ? Comment fait-on pour trouver A ? Venez m'écouter pour le savoir !

Venez nombreux !