Aufgabe 1:  (21.05.2025)

Dokumentieren Sie alle Programme, die Sie im Computer­labor geschrieben haben, mit den Programm­codes und zugehörigen Erklärungen.

• Versehen Sie Ihre Programm­codes mit Kommentaren. Schreiben Sie insbesondere zu jeder Funktion einen Kommentar, aus dem hervorgeht, was die Funktion tut, welche Argumente sie erwartet und was sie als Funktions­wert zurückgibt.

   

• In Ihrem erläuternden Text beschreiben Sie den theoretischen Hintergrund und die Eigen­schaften Ihrer Implementierung.

  Sie dürfen die Texte auf meinen Webseiten, aus meinem Buch oder auch aus anderen Quellen verwenden. Bemühen Sie sich aber dennoch, Ihre eigenen Überlegungen und Ihren eigenen Stil sichtbar werden zu lassen.

Aufgabe 2:  (11.06.2025)

Wenn Sie zwei Polynome vom Grad n miteinander multiplizieren, so benötigen Sie n² Schritte, wenn Sie jeden der n Koeffizienten des einen Polynoms mit jedem der n Koeffizienten des anderen Polynoms multiplizieren.

Sie beschleunigen die Polynom-Multi­plikation erheblich, wenn Sie die Polynome vorher von der Koeffizientendarstellung in die Stützstellen­darstellung trans­formieren, dann in dieser Darstellung in n Schritten multiplizieren, und dann wieder zurück­trans­formieren. Die Trans­formation und die Rück­trans­formation benötigen lediglich n·log(n) Schritte. Insgesamt kommen Sie also bei dieser indirekten Methode mit etwa 2·n·log(n) Schritten aus, gegenüber den n² Schritten bei der direkten Methode.

Grundsätzlich kommt die Fourier­transformation hierfür in Frage; jedoch speziell für die Polynomringe zugeschnitten, die in der Kryptografie verwendet werden, ist die als number-theoretic transform (NTT) bezeichnete Trans­formation.

1. Erarbeiten Sie sich die Theorie der NTT in der Version, die für das Signatur-Verfahren Dilithium verwendet wird, anhand von Quellen aus dem Internet bzw. auch aus Youtube-Videos (zum Beispiel https://www.youtube.com/watch?v=ey1ND xPITw).
2. Programmieren Sie die NTT und trans­formieren Sie das Polynom [99 52 0 7 0 29 33 100]  ∈  ℤ₁₁₃[x] / (x⁸ + 1). Die Darstellung des Polynoms als Vektor ist hier "little-endian", mit der 99 als Koeffizient von x⁰.
3. Programmieren Sie auch die Rück­trans­formation NTT^-1.
4. Multi­plizieren Sie die Polynome a = [99 52 0 7 0 29 33 100] und b = [6 0 45 12 14 78 65 112]  ∈  ℤ₁₁₃[x] / (x⁸ + 1) per Trans­formation, komponenten­weiser Multi­plikation und anschließender Rück­trans­formation.

Zur Kontrolle: Für das Polynom a = [99 52 0 7 0 29 33 100] ist a' = [78 59 59 62 65 60 81 102] das Ergebnis der NTT. Das Produkt c = a·b der beiden Polynome a und b ist c = [75 92 86 84 4 99 25 86].