====== std.crypto.ntt ======

Number Theoretic Transform (NTT) und Polynomring-Arithmetik für Post-Quantum-Kryptographie. Implementiert die Polynommultiplikation über R_q = Z_q[X]/(X²⁵⁶+1) für ML-KEM (q=3329) und ML-DSA (q=8380417). Diese Unit ist eine **interne Implementierungseinheit** — sie wird direkt von ML-KEM, ML-DSA und SLH-DSA genutzt, nicht von Anwendungscode.

<code lyx>
import std.crypto.ntt;
</code>

→ [[lyx_-_programmiersprache:units:crypto|std.crypto]] · [[lyx_-_programmiersprache:units:crypto:pqc|std.crypto.pqc]] · [[lyx_-_programmiersprache:units|Standard Library]]

**Hinweis:** Für PQC-Kryptographie → [[lyx_-_programmiersprache:units:crypto:pqc:mlkem|std.crypto.pqc.mlkem]] oder [[lyx_-_programmiersprache:units:crypto:pqc:pqc|std.crypto.pqc.pqc]] verwenden. Diese Unit ist nur relevant wenn eigene NTT-basierte Konstruktionen benötigt werden.

----

===== Konstanten =====

^ Konstante ^ Wert ^ Bedeutung ^
| ''POLY_BYTES'' | 2048 | Bytes pro Polynom (256 × int64) |
| ''KYBER_Q'' | 3329 | Modulus für ML-KEM (FIPS 203) |
| ''DILITH_Q'' | 8380417 | Modulus für ML-DSA (FIPS 204) |

----

===== Funktionen =====

**Polynom-Allokation:**

^ Funktion ^ Beschreibung ^
| ''NTTPolyNew(): int64'' | Allokiert 2048-Byte-Polynom-Puffer (256 × int64 = 256 Koeffizienten) |
| ''NTTPolyFree(p)'' | Gibt Polynom-Puffer frei |

**ML-KEM / Kyber (q = 3329):**

^ Funktion ^ Beschreibung ^
| ''KyberNTT(f)'' | NTT in-place (Fourier-Transformation über Z₃₃₂₉) |
| ''KyberINTT(f)'' | Inverse NTT in-place |
| ''KyberPolyMul(fa, fb, fc)'' | fc = fa × fb (Koeffizient-weise im NTT-Bereich) |
| ''KyberPolyAdd(fa, fb, fc)'' | fc = fa + fb |
| ''KyberPolySub(fa, fb, fc)'' | fc = fa − fb |
| ''KyberPolyReduce(f)'' | Reduziert alle Koeffizienten mod q |
| ''KyberPolyCopy(src, dst)'' | Kopiert Polynom |
| ''KyberPolyZero(f)'' | Setzt alle Koeffizienten auf 0 |
| ''KyberSampleNTT(seed, x, y, out)'' | Sampelt Polynom uniform aus Seed (SHAKE-128-basiert) |
| ''KyberSampleCBD(prf_out, eta, out)'' | Sampelt Polynom aus Centered Binomial Distribution |

**ML-DSA / Dilithium (q = 8380417):**

^ Funktion ^ Beschreibung ^
| ''DilithiumNTT(f)'' | NTT in-place (über Z₈₃₈₀₄₁₇) |
| ''DilithiumINTT(f)'' | Inverse NTT in-place |
| ''DilithiumPolyMul(fa, fb, fc)'' | fc = fa × fb im NTT-Bereich |
| ''DilithiumPolyAdd(fa, fb, fc)'' | fc = fa + fb |
| ''DilithiumPolySub(fa, fb, fc)'' | fc = fa − fb |

----

===== Mathematischer Hintergrund =====

Die NTT transformiert ein Polynom f ∈ R_q in den Frequenzbereich, wo Multiplikation zur komponentenweisen Multiplikation wird:

  NTT(f × g) = NTT(f) ∘ NTT(g)

Dies reduziert die Komplexität von Polynommultiplikation von O(n²) auf O(n log n).

**ML-KEM**: R_q = Z₃₃₂₉[X]/(X²⁵⁶+1), primitiver 512. Einheitswurzel ζ = 17\\
**ML-DSA**: R_q = Z₈₃₈₀₄₁₇[X]/(X²⁵⁶+1), primitiver 512. Einheitswurzel ζ = 1753

Letzte Aktualisierung: 2026-06-08