Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I've heard that it's possible to split up $GF(2^{128})$ into copies of several smaller fields like $GF(4)$ so as to make the math easier in some cases. How do you do that?
I know how it works for groups modulo a composite number using regular arithmetic instead of carryless, such as when using the Chinese Remainder Theorem to speed up RSA.
I believe that this is called "field extension".
When you have a finite field $\mathbb{K}$ of cardinal $q$ (necessarily, $q = p^m$ for some prime $p$ and integer $m$), then a finite field $\mathbb{K}'$ of cardinal $q^k$ can be defined for any integer $k$, in the following way. You consider $\mathbb{K}[X]$, which is the ring of polynomials whose coefficients are in $\mathbb{K}$. Polynomials can be added and multiplied together, and you can defined an euclidian division on polynomials. Then, choose some polynomial $P \in \mathbb{K}[X]$ of degree $k$. You can then consider polynomials of $\mathbb{K}[X]$ modulo $P$: these are all polynomials of degree up to $k-1$, and when you multiply two of them together, you do a division by $P$ and keep only the remainder.
These polynomials taken modulo $P$ form a ring of cardinal $q^k$. If you chose $P$ to be irreducible (i.e. there is no polynomial $R$ of degree strictly more than $1$ and strictly less than $k$ that divides $P$ exactly), then the ring you got is actually a finite field: that's your $\mathbb{K}'$. This is called a field extension because the elements of $\mathbb{K}$ naturally map to the polynomials of degree $0$ of $\mathbb{K}[X]$, so $\mathbb{K}$ can be said to be a subfield of $\mathbb{K}'$.
It may help to think of this construction as the same thing as the construction of complex numbers $\mathbb{C}$ over the reals $\mathbb{R}$: in $\mathbb{R}$, the polynomial $X^2+1$ is irreducible (there is no real whose square is $-1$); so we define complex numbers as $a+bX$, and then $(a+bX)(c+dX) = ac + (ad+bc)X + bdX^2$, that you take modulo $X^2+1$, i.e. by considering that $X^2=-1$. You then get $(a+bX)(c+dX) = (ac-bd) + (ad+bc)X$. Traditionally, you call that $X$ "$i$", and there you go: you have the complex numbers. With finite fields, you can do the same, with some extra possibilities because you can find irreducible polynomials of any degree (with real numbers, irreducible polynomials cannot have degree more than $2$).
For example, to define $GF(2^{128})$, you can start from $GF(2)$ (the field with two elements) and use an irreducible polynomial of degree $128$. However, you could also start with $GF(4)$ and use an irreducible polynomial of degree $64$: you will also end up with a finite field of cardinal $2^{64}$.
Of course, the field you start with, and the polynomial you choose, will matter for the field you actually get: if your values are represented as sequences of bits, and you compute things with them, the bit sequences you obtain depend on these parameters. However, and that is the "magic" thing, it so happens that when two finite fields have the same cardinal, then they are isomorphic to each other. In that sense, there is only one field of cardinal $2^{128}$, and all concrete fields that you can build are just different representations of that mathematical structure. This is why you can talk of "the" field $GF(2^{128})$.
Computing the isomorphism, i.e. mapping from one representation of $GF(2^{128})$ to another (e.g. to a representation as an extension of $GF(4)$ of degree $64$) can be a bit cumbersome, but, ultimately, it is "just linear" and similar to a change of basis with matrices.
To get some extended information on these matters, go read this book.
