## Thursday, November 29, 2012

### MISC: binary Galois Field multiplication

After reading NIST may not have you in mind, I decided that a new ISA should support binary Galois Field multiplication. Binary Galois Field is a special case of binary polynomial $$\mathbb{Z}_2[x]$$ where addition and subtraction are already supported as XOR, written as $$\oplus$$. What is missing for GF is multiplication and division in $$\mathbb{Z}_2[x]$$. The binary polynomials are expressed as bit vectors where the $$n$$-th bit is the coefficient of the $$x^n$$ term. Let $$\otimes$$ be polynomial multiplication.
• pmul: $$(a, b) \to (r, s)$$ where $$r s = a \otimes b$$, i.e. $$r$$ is the upper word of the result, and $$s$$ is the lower word.
• pdiv.mod: $$(a, b) \to (q, r)$$ where $$q \otimes b = a \oplus r$$, i.e. $$q$$ is the quotient and $$r$$ is the remainder.
It's been a while since I last studied abstract algebra, so I might not have gotten all my terminology correct, but you get the idea.