Skip to main content
added 88 characters in body
Source Link
Dilip Sarwate
  • 2.8k
  • 17
  • 24

GF$(2^8)$ or $\mathbb F_{2^8}$ can also be viewed as the vector space $\mathbb F_2^8$ of $8$-bit vectors (or bytes) over GF$(2)$ or $\mathbb F_2$. Suppose $\{\beta_0, \beta_1, \cdots, \beta_7\}$ is a basis of $\mathbb F_2^8$ over $\mathbb F_2$, that is, the sum $$a_0\beta_0 \oplus a_1\beta_1 \oplus \cdots \oplus a_7\beta_7, ~ a_i \in \mathbb F_2$$ equals $\mathbf 0$ if and only if all $8$ $a_i$ equal $0$. Then, every element $\gamma$ of $\mathbb F_{2^8}$ can be expressed as a $8$-bit vector $(\gamma_0, \gamma_1, \cdots, \gamma_7)$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$ meaning that $$\gamma = \gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7, ~ \gamma_i \in \mathbb F_2$$ with the property that $$\gamma + \delta = (\gamma_0, \gamma_1, \cdots, \gamma_7)\oplus (\delta_0, \delta_1, \cdots, \delta_7)$$ that is, _field additionfield addition is just the XOR sum of the $8$-bit representations with respect to the chosen basis; indeed, we do not even need to know the basis at all. Multiplication is more complicated and does require knowledge of the basis. We have that $$\begin{align} \gamma\otimes \delta &= (\gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7)\\ &= \sum_{i=0}^7\sum_{j=0}^7 \gamma_i \delta_j \beta_i\beta_j\\ &= (\gamma_0, \gamma_1, \cdots, \gamma_7)A(\delta_0, \delta_1, \cdots, \delta_7)^T \tag{1} \end{align}$$$$\begin{align} \gamma\otimes \delta &= (\gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7) \otimes(\delta_0\beta_0 \oplus \delta_1\beta_1 \oplus \cdots \oplus \delta_7\beta_7) \\ &= \sum_{i=0}^7\sum_{j=0}^7 \gamma_i \delta_j \beta_i\beta_j\\ &= (\gamma_0, \gamma_1, \cdots, \gamma_7)A(\delta_0, \delta_1, \cdots, \delta_7)^T \tag{1} \end{align}$$ where $A$ is a $8\times 8$ binary matrix whose entries can be figured out by expressing all the elements $\beta_i\beta_j$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$.

A commonly used basis (sometimes even referred to as a canonical polynomial basis) is $$\{\beta_0, \beta_1, \cdots, \beta_7\} = \{1, \alpha, \alpha^2, \cdots, \alpha^7\}$$ where $\alpha$ is a root of an irreducible binary polynomial of degree $8$. People have expended considerable effort in figuring out which degree-$8$ irreducible polynomial gives the sparsest matrix $A$ since this leads to reduced number of gates in a VLSI implementation. Multiplication can also be implemented as a process requiring several clock cycles instead of one clock cycle, in which case some different criteria may be used in figuring out which polynomial gives the cheapest or fastest implementation.

Polynomial bases are handy when one is doing calculations with paper and pencil (or on a blackboard!) because the calculations are easy to follow. But it is not necessary to stick to polynomial bases if one is interested in efficient hardware implementations. I am aware of at least one implementation where the dual of the polynomial basis is used, and several US patents have been issued for Galois field multiplications based on representations with respect to a normal basis (search for Massey-Omura multiplication). A normal basis is $$\{\alpha^{2^0}, \alpha^{2^1}, \alpha^{2^2}, \cdots, \alpha^{2^7}\}$$ where $\alpha$ is a root of a degree-$8$ irreducible binary polynomial whose degree-$7$ term is $1$ (the degree-$7$ term is the sum of all the basis elements and must not be $0$; else we do not have a basis at all). Note that squaring is a very simple operation with respect to a normal basis: the representation of $\gamma^2$ is just the right cyclic shift by one bit of the representation of $\gamma$.

I recommend the book by R.J.McEliece Finite Fields for Computer Scientists and Engineers, Kluwer Press, 1987 for lots of details on the matters described above.

GF$(2^8)$ or $\mathbb F_{2^8}$ can also be viewed as the vector space $\mathbb F_2^8$ of $8$-bit vectors (or bytes) over GF$(2)$ or $\mathbb F_2$. Suppose $\{\beta_0, \beta_1, \cdots, \beta_7\}$ is a basis of $\mathbb F_2^8$ over $\mathbb F_2$, that is, the sum $$a_0\beta_0 \oplus a_1\beta_1 \oplus \cdots \oplus a_7\beta_7, ~ a_i \in \mathbb F_2$$ equals $\mathbf 0$ if and only if all $8$ $a_i$ equal $0$. Then, every element $\gamma$ of $\mathbb F_{2^8}$ can be expressed as a $8$-bit vector $(\gamma_0, \gamma_1, \cdots, \gamma_7)$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$ meaning that $$\gamma = \gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7, ~ \gamma_i \in \mathbb F_2$$ with the property that $$\gamma + \delta = (\gamma_0, \gamma_1, \cdots, \gamma_7)\oplus (\delta_0, \delta_1, \cdots, \delta_7)$$ that is, _field addition is just the XOR sum of the $8$-bit representations with respect to the chosen basis; indeed, we do not even need to know the basis at all. Multiplication is more complicated and does require knowledge of the basis. We have that $$\begin{align} \gamma\otimes \delta &= (\gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7)\\ &= \sum_{i=0}^7\sum_{j=0}^7 \gamma_i \delta_j \beta_i\beta_j\\ &= (\gamma_0, \gamma_1, \cdots, \gamma_7)A(\delta_0, \delta_1, \cdots, \delta_7)^T \tag{1} \end{align}$$ where $A$ is a $8\times 8$ binary matrix whose entries can be figured out by expressing all the elements $\beta_i\beta_j$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$.

A commonly used basis (sometimes even referred to as a canonical polynomial basis) is $$\{\beta_0, \beta_1, \cdots, \beta_7\} = \{1, \alpha, \alpha^2, \cdots, \alpha^7\}$$ where $\alpha$ is a root of an irreducible binary polynomial of degree $8$. People have expended considerable effort in figuring out which degree-$8$ irreducible polynomial gives the sparsest matrix $A$ since this leads to reduced number of gates in a VLSI implementation. Multiplication can also be implemented as a process requiring several clock cycles instead of one clock cycle, in which case some different criteria may be used in figuring out which polynomial gives the cheapest or fastest implementation.

Polynomial bases are handy when one is doing calculations with paper and pencil (or on a blackboard!) because the calculations are easy to follow. But it is not necessary to stick to polynomial bases if one is interested in efficient hardware implementations. I am aware of at least one implementation where the dual of the polynomial basis is used, and several US patents have been issued for Galois field multiplications based on representations with respect to a normal basis (search for Massey-Omura multiplication). A normal basis is $$\{\alpha^{2^0}, \alpha^{2^1}, \alpha^{2^2}, \cdots, \alpha^{2^7}\}$$ where $\alpha$ is a root of a degree-$8$ irreducible binary polynomial whose degree-$7$ term is $1$ (the degree-$7$ term is the sum of all the basis elements and must not be $0$; else we do not have a basis at all). Note that squaring is a very simple operation with respect to a normal basis: the representation of $\gamma^2$ is just the right cyclic shift by one bit of the representation of $\gamma$.

I recommend the book by R.J.McEliece Finite Fields for Computer Scientists and Engineers, Kluwer Press, 1987 for lots of details on the matters described above.

GF$(2^8)$ or $\mathbb F_{2^8}$ can also be viewed as the vector space $\mathbb F_2^8$ of $8$-bit vectors (or bytes) over GF$(2)$ or $\mathbb F_2$. Suppose $\{\beta_0, \beta_1, \cdots, \beta_7\}$ is a basis of $\mathbb F_2^8$ over $\mathbb F_2$, that is, the sum $$a_0\beta_0 \oplus a_1\beta_1 \oplus \cdots \oplus a_7\beta_7, ~ a_i \in \mathbb F_2$$ equals $\mathbf 0$ if and only if all $8$ $a_i$ equal $0$. Then, every element $\gamma$ of $\mathbb F_{2^8}$ can be expressed as a $8$-bit vector $(\gamma_0, \gamma_1, \cdots, \gamma_7)$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$ meaning that $$\gamma = \gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7, ~ \gamma_i \in \mathbb F_2$$ with the property that $$\gamma + \delta = (\gamma_0, \gamma_1, \cdots, \gamma_7)\oplus (\delta_0, \delta_1, \cdots, \delta_7)$$ that is, field addition is just the XOR sum of the $8$-bit representations with respect to the chosen basis; indeed, we do not even need to know the basis at all. Multiplication is more complicated and does require knowledge of the basis. We have that $$\begin{align} \gamma\otimes \delta &= (\gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7) \otimes(\delta_0\beta_0 \oplus \delta_1\beta_1 \oplus \cdots \oplus \delta_7\beta_7) \\ &= \sum_{i=0}^7\sum_{j=0}^7 \gamma_i \delta_j \beta_i\beta_j\\ &= (\gamma_0, \gamma_1, \cdots, \gamma_7)A(\delta_0, \delta_1, \cdots, \delta_7)^T \tag{1} \end{align}$$ where $A$ is a $8\times 8$ binary matrix whose entries can be figured out by expressing all the elements $\beta_i\beta_j$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$.

A commonly used basis (sometimes even referred to as a canonical polynomial basis) is $$\{\beta_0, \beta_1, \cdots, \beta_7\} = \{1, \alpha, \alpha^2, \cdots, \alpha^7\}$$ where $\alpha$ is a root of an irreducible binary polynomial of degree $8$. People have expended considerable effort in figuring out which degree-$8$ irreducible polynomial gives the sparsest matrix $A$ since this leads to reduced number of gates in a VLSI implementation. Multiplication can also be implemented as a process requiring several clock cycles instead of one clock cycle, in which case some different criteria may be used in figuring out which polynomial gives the cheapest or fastest implementation.

Polynomial bases are handy when one is doing calculations with paper and pencil (or on a blackboard!) because the calculations are easy to follow. But it is not necessary to stick to polynomial bases if one is interested in efficient hardware implementations. I am aware of at least one implementation where the dual of the polynomial basis is used, and several US patents have been issued for Galois field multiplications based on representations with respect to a normal basis (search for Massey-Omura multiplication). A normal basis is $$\{\alpha^{2^0}, \alpha^{2^1}, \alpha^{2^2}, \cdots, \alpha^{2^7}\}$$ where $\alpha$ is a root of a degree-$8$ irreducible binary polynomial whose degree-$7$ term is $1$ (the degree-$7$ term is the sum of all the basis elements and must not be $0$; else we do not have a basis at all). Note that squaring is a very simple operation with respect to a normal basis: the representation of $\gamma^2$ is just the right cyclic shift by one bit of the representation of $\gamma$.

I recommend the book by R.J.McEliece Finite Fields for Computer Scientists and Engineers, Kluwer Press, 1987 for lots of details on the matters described above.

Source Link
Dilip Sarwate
  • 2.8k
  • 17
  • 24

GF$(2^8)$ or $\mathbb F_{2^8}$ can also be viewed as the vector space $\mathbb F_2^8$ of $8$-bit vectors (or bytes) over GF$(2)$ or $\mathbb F_2$. Suppose $\{\beta_0, \beta_1, \cdots, \beta_7\}$ is a basis of $\mathbb F_2^8$ over $\mathbb F_2$, that is, the sum $$a_0\beta_0 \oplus a_1\beta_1 \oplus \cdots \oplus a_7\beta_7, ~ a_i \in \mathbb F_2$$ equals $\mathbf 0$ if and only if all $8$ $a_i$ equal $0$. Then, every element $\gamma$ of $\mathbb F_{2^8}$ can be expressed as a $8$-bit vector $(\gamma_0, \gamma_1, \cdots, \gamma_7)$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$ meaning that $$\gamma = \gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7, ~ \gamma_i \in \mathbb F_2$$ with the property that $$\gamma + \delta = (\gamma_0, \gamma_1, \cdots, \gamma_7)\oplus (\delta_0, \delta_1, \cdots, \delta_7)$$ that is, _field addition is just the XOR sum of the $8$-bit representations with respect to the chosen basis; indeed, we do not even need to know the basis at all. Multiplication is more complicated and does require knowledge of the basis. We have that $$\begin{align} \gamma\otimes \delta &= (\gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7)\\ &= \sum_{i=0}^7\sum_{j=0}^7 \gamma_i \delta_j \beta_i\beta_j\\ &= (\gamma_0, \gamma_1, \cdots, \gamma_7)A(\delta_0, \delta_1, \cdots, \delta_7)^T \tag{1} \end{align}$$ where $A$ is a $8\times 8$ binary matrix whose entries can be figured out by expressing all the elements $\beta_i\beta_j$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$.

A commonly used basis (sometimes even referred to as a canonical polynomial basis) is $$\{\beta_0, \beta_1, \cdots, \beta_7\} = \{1, \alpha, \alpha^2, \cdots, \alpha^7\}$$ where $\alpha$ is a root of an irreducible binary polynomial of degree $8$. People have expended considerable effort in figuring out which degree-$8$ irreducible polynomial gives the sparsest matrix $A$ since this leads to reduced number of gates in a VLSI implementation. Multiplication can also be implemented as a process requiring several clock cycles instead of one clock cycle, in which case some different criteria may be used in figuring out which polynomial gives the cheapest or fastest implementation.

Polynomial bases are handy when one is doing calculations with paper and pencil (or on a blackboard!) because the calculations are easy to follow. But it is not necessary to stick to polynomial bases if one is interested in efficient hardware implementations. I am aware of at least one implementation where the dual of the polynomial basis is used, and several US patents have been issued for Galois field multiplications based on representations with respect to a normal basis (search for Massey-Omura multiplication). A normal basis is $$\{\alpha^{2^0}, \alpha^{2^1}, \alpha^{2^2}, \cdots, \alpha^{2^7}\}$$ where $\alpha$ is a root of a degree-$8$ irreducible binary polynomial whose degree-$7$ term is $1$ (the degree-$7$ term is the sum of all the basis elements and must not be $0$; else we do not have a basis at all). Note that squaring is a very simple operation with respect to a normal basis: the representation of $\gamma^2$ is just the right cyclic shift by one bit of the representation of $\gamma$.

I recommend the book by R.J.McEliece Finite Fields for Computer Scientists and Engineers, Kluwer Press, 1987 for lots of details on the matters described above.