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.
import std.crypto.ntt;
→ std.crypto · std.crypto.pqc · Standard Library
Hinweis: Für PQC-Kryptographie → std.crypto.pqc.mlkem oder std.crypto.pqc.pqc verwenden. Diese Unit ist nur relevant wenn eigene NTT-basierte Konstruktionen benötigt werden.
| 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) |
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 |
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