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?

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.