Siguiente: Field operations with the Arriba: Multiplication in Finite Fields Anterior: Ring multiplication

Representation of Galois fields of characteristic 2

Let $\mathbb{F}_2=\{0,1\}$ be the prime Galois field consisting of just two elements. For most integer values $n\geq 2$ there is a minimum $k$, with $0<k<n$, such that the polynomial $p_{nk}(X) = X^n + X^k + 1$ is irreducible over the field $\mathbb{F}_2$. In Table 6 we display such pairs $(n:k)$, for $n=2,\ldots,101$. The cases in which there is no such $k$ are distinguished by making $k=n$, in them any irreducible polynomial of degree $n$ shall involve more than one intermediate powers $X^k$. Whenever $p_{nk}(X)$ is irreducible, the Galois field $\mathbb{F}_{2^n}$ is isomorphic to the quotient $\mathbb{F}_2[X]/\left(p_{nk}(X)\right)$, and, consequently, the arithmetic in the field can be realized as the polynomial arithmetic reduced modulus $p_{nk}(X)$. Each element in $\mathbb{F}_{2^n}$ is of the form $p_{\mbox{\scriptsize\boldmath$\epsilon$}}(X) = \sum_{i=1}^{n} \epsilon_i X^{i-1}$ and is naturally identified with the integer $I_{\mbox{\scriptsize\boldmath$\epsilon$}} = \sum_{i=1}^{n} \epsilon_i 2^{i-1} \in [\![0,2^n-1]\!]$.

Table 6: Pairs $(n:k)$ such that $p_{nk}(X) = X^n + X^k + 1$ is an irreducible polynomial over the field $\mathbb{F}_2$.

(2 : 1)	(3 : 1)	(4 : 1)	(5 : 2)	(6 : 1)	(7 : 1)	(8 : 2)	(9 : 1)	(10 : 3)	(11 : 2)
(12 : 2)	(13 : 13)	(14 : 2)	(15 : 1)	(16 : 4)	(17 : 3)	(18 : 2)	(19 : 19)	(20 : 3)	(21 : 2)
(22 : 1)	(23 : 5)	(24 : 4)	(25 : 3)	(26 : 26)	(27 : 27)	(28 : 1)	(29 : 2)	(30 : 1)	(31 : 3)
(32 : 8)	(33 : 10)	(34 : 6)	(35 : 2)	(36 : 4)	(37 : 37)	(38 : 38)	(39 : 4)	(40 : 6)	(41 : 3)
(42 : 4)	(43 : 43)	(44 : 2)	(45 : 45)	(46 : 1)	(47 : 5)	(48 : 8)	(49 : 9)	(50 : 6)	(51 : 51)
(52 : 3)	(53 : 53)	(54 : 9)	(55 : 7)	(56 : 2)	(57 : 4)	(58 : 4)	(59 : 59)	(60 : 1)	(61 : 61)
(62 : 6)	(63 : 1)	(64 : 16)	(65 : 18)	(66 : 3)	(67 : 67)	(68 : 9)	(69 : 69)	(70 : 4)	(71 : 6)
(72 : 8)	(73 : 25)	(74 : 35)	(75 : 75)	(76 : 21)	(77 : 77)	(78 : 8)	(79 : 9)	(80 : 12)	(81 : 4)
(82 : 6)	(83 : 83)	(84 : 5)	(85 : 85)	(86 : 21)	(87 : 13)	(88 : 4)	(89 : 38)	(90 : 27)	(91 : 91)
(92 : 2)	(93 : 2)	(94 : 10)	(95 : 11)	(96 : 16)	(97 : 6)	(98 : 11)	(99 : 99)	(100 : 12)	(101 : 101)

Siguiente: Field operations with the Arriba: Multiplication in Finite Fields Anterior: Ring multiplication