La cryptographie post-quantique fondée sur les réseaux euclidiens multiplie à de nombreuses reprises des polynômes de degré n = 256. Si la méthode naïve qui multiplie tous les couples de coefficients nécessite environ n² multiplications et la méthode utilisant la transformée en théorie des nombres (NTT) environ n log₂ n, quelle valeur est la plus proche du facteur par lequel la NTT réduit le nombre de multiplications ?

Réponse : B. Environ 1/32

La méthode naïve nécessite n² = 256² = 65 536 multiplications et la méthode NTT n log₂ n = 256 × 8 = 2048 ; 65 536 ÷ 2048 = 32, soit une réduction à environ 1/32. La transformée en théorie des nombres applique l'idée de la transformée de Fourier rapide aux entiers modulo un nombre premier, et après la transformation, seule une multiplication coefficient par coefficient est nécessaire. ML-KEM traite les coefficients modulo q = 3329 et est conçu pour être calculé avec la NTT ; les circuits NTT sont donc un composant central des accélérateurs de cryptographie post-quantique. En outre, ML-KEM et ML-DSA utilisent beaucoup de fonctions de la famille SHA-3 (SHAKE) pour générer des matrices et des valeurs aléatoires ; des accélérateurs pour celles-ci sont donc aussi efficaces.