CLMUL
# CLMUL

Carry-less Multiplication (CLMUL) (dt.: übertragsfreie Multiplikation) ist eine Befehlserweiterung der x86-Prozessorarchitektur, die eine schnelle, hardwareunterstützte Berechnung in Bereichen aus der Zahlentheorie ermöglicht. Die Befehlserweiterung wurde im Jahr 2008 von Intel vorgeschlagen und ab 2010 bei der Westmere-Mikroarchitektur eingeführt. Sie ist in allen Intel-Prozessoren ab der Intel-Haswell-Mikroarchitektur und AMD-Prozessoren ab AMD Bulldozer verfügbar.

Übertragsfrei bedeutet hier $1+1=0.$ Die Zwischensummen bei der Multiplikation werden bitweise durch XOR-Verknüpfung gebildet.

Anwendungsbeispiele sind die Kryptografie bei Blockverschlüsselungen im Betriebsmodus Galois/Counter Mode (GCM), welcher auf Berechnungen in einem Galoiskörper basiert. Ein anderes Anwendungsfeld sind die Erzeugung von Prüfsummen im Bereich der zyklischen Redundanzprüfungen (CRC).

## Übertragsfreies Produkt

Seien $a$ und $b$ Zahlen mit den Binärdarstellungen $(a_{n-1}\ldots a_{1}a_{0})_{2}$ bzw. $(b_{n-1}\ldots b_{1}b_{0})_{2}$. Das übertragsfreie Produkt ist dann wie folgt definiert:

    $\operatorname {clmul} (a,b)=\bigoplus _{k,l=0}^{n}2^{k+l}a_{k}b_{l}$,

wobei $\oplus$ die bitweise XOR-Verknüpfung darstellt. Der Zusatz „übertragsfrei“ wird klar, wenn man obigen Ausdruck mit der regulären Multiplikation vergleicht:

    $ab=\sum _{k,l=0}^{n}2^{k+l}a_{k}b_{l}$

wo wegen der Summe immer dann ein Übertrag in das Bit $k+l+1$ notwendig ist, wenn $a_{k}=b_{l}=1$. Da aber $1\oplus 1=0$, fällt der Übertrag in clmul weg. Wegen der einfacheren Berechnung ergibt sich folgende einfache Binärdarstellung $(c_{n-1}\ldots c_{1}c_{0})_{2}$ für das übertragsfreie Produkt:

    $c_{l}=\bigoplus _{k=0}^{l}a_{k}b_{l-k}$.

Das übertragsfreie Produkt hat ähnliche Eigenschaften wie das reguläre Produkt:

* Kommutativgesetz: $\operatorname {clmul} (a,b)=\operatorname {clmul} (b,a)$
* Assoziativgesetz: $\operatorname {clmul} (a,\operatorname {clmul} (b,c))=\operatorname {clmul} (\operatorname {clmul} (a,b),c)$
* Distributivgesetz: $\operatorname {clmul} (a,b\oplus c))=\operatorname {clmul} (a,b)\oplus \operatorname {clmul} (a,c)$

## Befehlssatzerweiterung

Die Befehle aus der Erweiterung berechnen aus den Eingabewerten von zwei 64 Bit das übertragsfreie Produkt von 128 Bit und legen das Ergebnis in einem 128 Bit breiten XMM-Register ab. Als Quelle für die beiden Faktoren kann je nach Adressierungsmodus entweder ein anderes XMM-Register, dann werden die beiden 64 Bit breiten Hälften eines XMM-Registers als zwei Faktoren betrachtet, oder die Hälften von zwei verschiedenen XMM-Registern oder eine Speicheradresse im Hauptspeicher angegeben werden.

Die Multiplikation von zwei 128 bit breiten Eingabewerten kann mit Hilfe des Karazuba-Algorithmus in vier Rechenschritten erfolgen.

