Français
Menu

Qu'est-ce que Transformée en théorie des nombres ?

Transformation qui applique l'idée de la transformée de Fourier rapide aux entiers modulo un nombre premier. Elle remplace la multiplication de polynômes par une transformation, une multiplication coefficient par coefficient et une transformation inverse, ce qui ramène les quelque n² multiplications nécessaires pour un degré n à environ n log n. Elle ne demande que des calculs exacts sur des entiers, sans erreur d'arrondi. Elle est au cœur des calculs de la cryptographie post-quantique fondée sur les réseaux euclidiens, comme ML-KEM et ML-DSA, et son accélération par des circuits dédiés est à l'étude.

Nom japonais: 数論変換

« Transformée en théorie des nombres » apparaît dans 1 questions d'entraînement réparties sur 1 thèmes, dont Sécurité matérielle : évolutions récentes.

Domaine: Sécurité matérielle : évolutions récentes

S'entraîner : questions sur Transformée en théorie des nombres

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 ?

  1. AEnviron 1/8
  2. BEnviron 1/32
  3. CEnviron 1/256
Afficher la réponse et l'explication

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.

« Transformée en théorie des nombres » dans les explications

Questions mentionnant « Transformée en théorie des nombres » (1)

  1. 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 ?

Termes associés

Cryptographie post-quantique (PQC) Transformée de Fourier rapide (FFT) Opération modulo ML-KEM Arm CCA (Confidential Compute Architecture) Attaque par exécution transitoire Authentification de pointeurs (PAC) CHERI DICE (Device Identifier Composition Engine) FIPS 140-3

Retour au glossaire