Thomas Prest (École Normale Supérieure, Thales Communications and Security)

La transformée de Fourier rapide (FFT) permet de calculer en temps quasilinéaire le produit de deux polynômes dans l’anneau de convolution R [ x ]/( x d-1), une tâche qui nécessiterait un temps quadratique de manière naïve. De manière équivalente, elle permet d’accélérer les produits matrice-vecteur quand la matrice est circulante.

Dans nos travaux, nous montrons que les idées de la FFT peuvent être appliquées à l’orthogonalisation de matrices circulantes (par blocs de taille d*d ). Lorsque d est friable, l’orthogonalisation de Gram-Schmidt (GSO) peut être réalisée de manière récursive, ce qui permet de calculer une représentation factorisée et creuse de la GSO de taille O ( d log d ). À son tour, cette décomposition de la GSO accélère un algorithme central sur les réseaux: l’algorithme Nearest Plane de Babai. Dans les deux cas, les complexités en temps et en espace de nos algorithmes sont en O ( d log d ).

Nos résultats s’étendent aux anneaux cyclotomiques, ainsi qu’au sampler de Klein, une version probabiliste de l’algorithme nearest plane. La principale application est d’accélérer la cryptographie sur les réseaux euclidiens.