Deutsch
Menü

Was ist Zahlentheoretische Transformation (Number-Theoretic Transform)?

Transformation, die das Prinzip der schnellen Fourier-Transformation auf ganze Zahlen modulo einer Primzahl überträgt. Sie ersetzt die Polynommultiplikation durch eine Transformation, koeffizientenweise Multiplikation und eine Rücktransformation und verringert so die für Grad n benötigten rund n² Multiplikationen auf rund n log n. Sie kommt mit exakter Ganzzahlarithmetik ohne Rundungsfehler aus. Sie bildet den Kern der Berechnungen gitterbasierter Post-Quanten-Kryptografie wie ML-KEM und ML-DSA, und ihre Beschleunigung mit dedizierten Schaltungen wird vorangetrieben.

Japanische Bezeichnung: 数論変換

„Zahlentheoretische Transformation (Number-Theoretic Transform)“ kommt in 1 Übungsfragen aus 1 Themen vor, z. B. Aktuelle Entwicklungen der Hardwaresicherheit.

Fachgebiet: Aktuelle Entwicklungen der Hardwaresicherheit

Jetzt üben: Fragen zu Zahlentheoretische Transformation (Number-Theoretic Transform)

In gitterbasierter Post-Quanten-Kryptografie werden wiederholt Polynome vom Grad n = 256 multipliziert. Benötigt das naive Verfahren, bei dem alle Koeffizientenpaare multipliziert werden, etwa n² Multiplikationen und das Verfahren mit der zahlentheoretischen Transformation (NTT) etwa n log₂ n, auf etwa welchen Bruchteil verringert die NTT die Zahl der Multiplikationen? Welcher Wert liegt am nächsten?

  1. Aetwa 1/8
  2. Betwa 1/32
  3. Cetwa 1/256
Antwort und Erläuterung anzeigen

Antwort: B. etwa 1/32

Das naive Verfahren benötigt n² = 256² = 65.536 Multiplikationen, das NTT-Verfahren n log₂ n = 256 × 8 = 2048; wegen 65.536 ÷ 2048 = 32 sinkt die Zahl also auf etwa 1/32. Die zahlentheoretische Transformation überträgt das Prinzip der schnellen Fourier-Transformation auf ganze Zahlen modulo einer Primzahl; nach der Transformation sind nur noch koeffizientenweise Multiplikationen nötig. ML-KEM rechnet mit Koeffizienten modulo q = 3329 und ist darauf ausgelegt, mit der NTT berechnet zu werden, weshalb NTT-Schaltungen ein zentraler Baustein von Beschleunigern für Post-Quanten-Kryptografie sind. Außerdem nutzen ML-KEM und ML-DSA zur Erzeugung von Matrizen und Zufallswerten intensiv Funktionen der SHA-3-Familie (SHAKE), sodass auch Beschleuniger dafür wirksam sind.

„Zahlentheoretische Transformation (Number-Theoretic Transform)“ in den Erläuterungen

Fragen mit „Zahlentheoretische Transformation (Number-Theoretic Transform)“ (1)

  1. In gitterbasierter Post-Quanten-Kryptografie werden wiederholt Polynome vom Grad n = 256 multipliziert. Benötigt das naive Verfahren, bei dem alle Koeffizientenpaare multipliziert werden, etwa n² Multiplikationen und das Verfahren mit der zahlentheoretischen Transformation (NTT) etwa n log₂ n, auf etwa welchen Bruchteil verringert die NTT die Zahl der Multiplikationen? Welcher Wert liegt am nächsten?

Verwandte Begriffe

Post-Quanten-Kryptografie (PQC) Schnelle Fourier-Transformation (FFT) ML-KEM Arm CCA (Confidential Compute Architecture) CHERI Confidential Computing DICE (Device Identifier Composition Engine) FIPS 140-3 HBOM (Hardware-Stückliste) Kontrollflussintegrität (Control-Flow Integrity)

Zur Glossarübersicht