In Section \ref{Sec:Vectors} we have introduced nibbles and bytes, respectively, as
vectors of four bits and of eight bits.
So a nibble could be \(0100\) and a byte could be \(00111010\).
We first have a special look at nibbles, then we relate them to bytes, and finally
we compare this approach with the polynomial notation.
In computer science it is very useful to represent long strings of bits in a compact way.
For this aim, we use hexadecimal notation, i.e. the notation for numbers in base \(16\). This notation system uses sixteen symbols, i.e. the usual symbols 0-9 to represent numbers from 0 to 9 and then the letters A, B, C, D, E, F for the numbers from ten to sixteen.
Each hexadecimal symbol represents a nibble, i.e. four bits, as shown in the following table
| Decimal | Bits | Polynomials | Hex |
|---|---|---|---|
| \(0\) | \(0000\) | \(0\) | \(0\) |
| \(1\) | \(0001\) | \(1\) | \(1\) |
| \(2\) | \(0010\) | \(x\) | \(2\) |
| \(3\) | \(0011\) | \(x+1\) | \(3\) |
| \(4\) | \(0100\) | \(x^{2}\) | \(4\) |
| \(5\) | \(0101\) | \(x^{2}+1\) | \(5\) |
| \(6\) | \(0110\) | \(x^{2}+x\) | \(6\) |
| \(7\) | \(0111\) | \(x^{2}+x+1\) | \(7\) |
| \(8\) | \(1000\) | \(x^{3}\) | \(8\) |
| \(9\) | \(1001\) | \(x^{3}+1\) | \(9\) |
| \(10\) | \(1010\) | \(x^{3}+x\) | \(A\) |
| \(11\) | \(1011\) | \(x^{3}+x+1\) | \(B\) |
| \(12\) | \(1100\) | \(x^{3}+x^{2}\) | \(C\) |
| \(13\) | \(1101\) | \(x^{3}+x^{2}+1\) | \(D\) |
| \(14\) | \(1110\) | \(x^{3}+x^{2}+x\) | \(E\) |
| \(15\) | \(1111\) | \(x^{3}+x^{2}+x+1\) | \(F\) |
In order to convert from binary to hexadecimal notation we perform the following steps:
group the bits in nibbles from right to left;
convert each nibble in an hexadecimal digit as in the table above.
On the other hands, to convert from hexadecimal to binary notation
using the table above, write each hexadecimal digit as a nibble;
juxtapose the results.
The vector \(00010101\) is formed by the two nibbles \(0001\) \(0101\) represented as \(0x15\), corresponding to the decimal \(21\). The vector \(11100111\) is formed by the nibbles \(1110\) \(0111\), with the notation \(0xE7\), corresponding to the decimal \(231\).
Find the hex representation of the following strings:
\(11110100\);
\(01100010\);
\(11100010\).
Find the binary representation of the following hexadecimal numbers: \(AF\), \(A0\) and \(B5\).
A byte is a vector of \(8\) bits, so it is formed by two nibbles. Then, we can represent it with two ”hex digits”, as we have done in Example \ref{BitHex}.
We can also represent bytes as polynomials: in particular if \(a_{7}a_{6}a_{5}a_{4}a_{3}a_{2}a_{1}a_{0}\) is the binary vector representing a byte, we have the following representation
The byte \(10101011\), corresponding to the hex notation \(0xAB\), can also be denoted by the polynomial \(x^{7}+x^{5}+x^{3}+x+1\).
The polynomial notation for bytes is important because we can multiply bytes by means of polynomial multiplication, which turns out to be important for cryptographic applications. Let us see an example.
Suppose we want to multiply \(0xAB\) by \(0x4F\). Then, we first convert these numbers from the hex notation to the binary notation:
\begin{equation} 0xAB=10101011,\qquad 0x4F=01001111.\nonumber \\ \end{equation}From the binary notation, we can get the corresponding polynomials:
\begin{equation} 0xAB=x^{7}+x^{5}+x^{3}+x+1\qquad 0x4F=x^{6}+x^{3}+x^{2}+x+1.\nonumber \\ \end{equation}Multiplying the polynomials is now an easy task; we only have to remember that, since we are dealing with bytes we need to take the reminder by \(g_{256}=x^{8}+x^{4}+x^{3}+x^{2}+1\). So
\begin{equation} 0xAB\cdot 0x4F\rightarrow(x^{7}+x^{5}+x^{3}+x+1)(x^{6}+x^{3}+x^{2}+x+1)=\nonumber \\ \end{equation} \begin{equation} x^{13}+x^{11}+x^{10}+x^{7}+x^{6}+x^{3}+1=x^{7}+x^{6}+x^{4}+x\nonumber \\ \end{equation}The result is \(x^{7}+x^{6}+x^{4}+x=11010010=0xD2\).
Suppose we want to perform the bytes multiplication \(88\cdot 88\), where each byte is represented in decimal form. In its binary form, \(88\) is \(01011000\), whereas its hex form is \(0x58\) and it can be represented as the polynomial \(f=x^{6}+x^{4}+x^{3}\). An easy computation shows that
\begin{equation} f^{2}=(x^{6}+x^{4}+x^{3})^{2}=\underline{x^{12}}+x^{8}+x^{6}\,=^{\mathrm{substitution}}\,\underline{x^{8}+x^{7}+x^{6}+x^{4}}+x^{8}+x^{6}=x^{7}+x^{4}\,,\nonumber \\ \end{equation}whose representation in binary form is \(10010000\), in hex notation is \(0x90\) and in decimal form is \(144\).
Perform the following byte multiplications and write the results in the notations: hexadecimal, binary, polynomials, decimal.
\(0xCA\cdot 0x1C\);
\(01010000\cdot 10100100\);
\(0x4A\cdot 0x6D\)
\(11\cdot 49\)