Séquences pseudo-aléatoires et récurrences linéaires à coefficients polynomiaux

• Alexis Bonnecaze de l'équipe SIS de l'Université de Toulon et du Var.
• Patrick Solé de l'équipe RECIFE de l'I3S.
• le projet CAFE de l'INRIA

Ce projet 2002 est terminé, voici un court bilan:

• En collaboration avec P.Solé (I3S) et P.Gaborit (Limoges), nous avons étudié un analogue polynomial du cryptosystème NTRU appelé CTRU. Julien Ohler (Université de Toulon et du Var) a fait son stage en alternance entre Toulon et Sophia de mai à juillet 2002, co-encadré par M.Bronstein et P.Solé. Pendant ce stage, il a implémenté un prototype de ce nouveau cryptosystème en Aldor dans la bibliothèque Algebra, ainsi qu'une attaque sur clé basée sur la forme de Popov de matrices de polynômes. Ce travail a donné lieu à la publication du rapport de recherche INRIA RR-4621.
• En collaboration avec P.Solé (I3S), nous avons étudié la périodicité de séquences linéaires générées sur un corps fini par une récurrence à coefficients polynomiaux, et avons rédigé un article contenant une preuve de leur périodicité et des algorithmes pour passer entre les diverses représentations de ces séquences (à paraître dans le Journal of Complexity). Durant la seconde partie de son stage, Julien Ohler a aussi fourni une implémentation de ces algorithmes, dont plusieurs composantes vont faire partie de la prochaine version de la bibliothèque Algebra du projet CAFE.