Modulus operation for polynomials over GF(2)

Question

If I treat the coefficients as an array of boolean values, I would achieve multiplication by using the AND operator and addition by using XOR. How would I go about finding the remainder? Is there, analogous to the other operations, a logic gate that would yield the appropriate result when applied to the coefficients?

Answer 1

If I am understanding your question correctly you want to know how to perform the following operation:

\begin{equation} \text{mod} : (n,k) \mapsto \min_{q \in \mathbb{N}} \{ n-qk \} \end{equation} i.e. remainder after division but for GF(2). There is only one meaningful way to define this function for GF(2) and that is to set $\text{mod}(n,k) = 0$ for all values $(n,k)$. The reason is that GF(2) is a field and therefore "for all $n,k$ there exists a $q$ such that $kq = n$," the $q$ in the statement is the number $k^{-1}n$. "What is $k^{-1}?$" you may ask, well a field always contains a multiplicative inverse for all of its elements so the existence of $k^{-1}$ is guaranteed by the definition of a field. You should work out the multiplication table of the AND operation to verify that GF(2) is indeed a field.