Jeudi 1 décembre 2011 à 10h30 en salle C49
Sihem Mesnager (Université Paris VIII)

Titre : Caractérisation efficace d'une famille de fonctions hyper-courbes

Résumé :
Une fonction booléenne avec un nombre pair de variables est dite "courbe" ("bent" dans la terminologie anglo-saxonne) si sa non-linéarité est maximale. Cela correspond à être à distance maximale pour la distance de Hamming de l'ensemble des fonctions booléennes linéaires, encore appelé code de Reed et Müller d'ordre 1. Les fonctions "hyper-courbes" forment une sous classe importante des fonctions courbes. Récemment, Lisonek a reformulé la caractérisation de Charpin et Gong d'une large classe de fonctions hyper-courbes en termes de cardinalités de certaines courbes hyperelliptiques. Dans cet exposé, nous montrons qu'une telle reformulation peut être naturellement étendue à une large famille de fonctions hyper-courbes proposée par Mesnager en 2010. Ceci nous a permis d'obtenir un test de complexité polynomiale de la propriété "hyper-courbe" . Nous montrons également comment une telle reformulation peut être transformée pour obtenir un test plus efficace.

Remarques : Attention au jour et à l'heure ! Travail en collaboration avec Jean-Pierre Flori.