Systematische Programmentwicklung Laboraufgaben

Computerlabor   10.11.2025

Aufgabe 13:  (Schnelle Polynom­multiplikation - korrigiert)

Multi­plizieren Sie die folgenden beiden Polynome mit Koeffizienten aus dem Körper ℤ113 (Arithmetik modulo 113, Python-Klasse ModInt) miteinander:

99·x0 + 52·x1 + 0·x2 + 7·x3 + 0·x4 + 29·x5 + 33·x6 + 100·x7   und

6·x0 + 0·x1 + 45·x2 + 12·x3 + 14·x4 + 78·x5 + 65·x6 + 112·x7

 

Multi­plizieren Sie die beiden Polynome, indem Sie

  • die Polynome (als Koeffizientenvektoren der Länge 16) jeweils mit der schnellen Fourier­transformation im Körper ℤ113 trans­formieren (16-te Einheits­wurzel w = 42),
  • die beiden Ergebnis­vektoren komponenten­weise multi­plizieren,
  • das Ergebnis mit der inversen Fourier­transformation zurück­trans­formieren.
Hinweis: Sie müssen die Koeffizientenvektoren der Polynome bis zur Länge 16 mit Nullen auf­füllen, damit die Fourier­transformation die Funktions­werte an 16 Stützstellen liefert. Diese benötigen Sie, weil das Ergebnis­polynom einen Grad bis zu  < 16 hat.

Bemerkung: In der Kryptografie wird das Ergebnis der Polynom­multiplikation noch modulo des Polynoms xn + 1 reduziert. Dies erreichen Sie, indem Sie die zweite Hälfte des betreffenden Koeffizientenvektors von der ersten Hälfte subtrahieren (modulo 113). Herauskommen sollte dann folgender Ergebnis­vektor

75 92 86 84 4 99 25 86

Hintergrund ist, dass modulo xn + 1 gerechnet gilt

xn + 1  ≡  0 (mod xn +1)  und damit
xn ≡ -1 (mod xn +1)  sowie
xn+1 ≡ -x (mod xn +1)  usw.

 

[up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden