Galois fields in cryptography I don't really understand Galois fields, but I've noticed they're used a lot in crypto. I tried to read into them, but quickly got lost in the mess of heiroglyphs and alien terms. I understand they're sets of the form $GF(p^n)$ for $n\geq1$ where $p$ is prime and $n$ is an integer. From what I can tell, they're defined as the following:

$GF(p^n) = [f(0) \bmod p, f(1) \bmod p, \dotsc, f(p^n-1) \bmod p,  f(p^n) \bmod p]$

for $f(x) = \sum_{i=0}^{n} \space x^ik_i$, i.e. an $n$-order polynomial with constants $K$.

I've seen mention that these fields are bijective, such that for an input set $A$ there is an output set $B$ containing the same values as $A$, but in a different order.

Is this correct? Does this have applications for creating s-boxes?

Update:
Thanks for the answers so far. I now understand that $GF(p^n)$ is an array of size-$n$ vectors, each element of which is computed as the result of some polynomial mod $p$, but I'm still not clear on the rest of it. I mostly understand how vector manipulation can be done on such a field, but I'm still non the wiser as to how I would use such a finite field, let alone impliment them in code. I don't really understand what $GF(p^n)$ looks like in terms of construction, which I guess is what I'm really looking for. If it's an array of vectors, each element of which is computed by some polynomial, how is the input to that polynomial decided? Is $GF$ a function, into which you provide such a value? Is the input value an integer, a vector, etc? If so, what's the meaning of the input value? How does the index of the vector in the set factor into the computation of its values?

For example:

$GF(p^n)[i] = \begin{bmatrix} v_0\\v_1\\v_2\\...\\v_{n-1} \end{bmatrix}$

Where $i$ is some index into the field, how are the vector elements $V$ computed? What inputs are provided?
The $GF$ in $GF(p^n)$ is not a function &mdash; it just stands for "Galois field (of $p^n$ elements)".

As for what a Galois field is, it's a finite set of things (which we might represent e.g. with the numbers from $0$ to $p^n-1$), with some mathematical operations (specifically, addition and multiplication, and their inverses) defined on them that let us calculate with these things as if they were ordinary numbers, but so that the results of the calculations always stay inside the finite set.

Specifically, we require the operations defined on the elements of this finite set to satisfy the field axioms, which include the usual associativity, commutativity and distributivity rules you probably learned in high school algebra class.  In particular, we also require every element $a$ to have an additive inverse $-a$ and (if $a \ne 0$) a multiplicative inverse $1/a$, such that $a + (-a) = 0$ and $a \times (1/a) = 1$.  Thus, as long as you just stick to algebraic manipulations using these rules, the Galois fields all look exactly like the field of real numbers you're familiar with.

To learn how to do arithmetic (i.e. actual calculations with actual numbers) in Galois fields, it's probably easiest (particularly if you're already familiar with modular arithmetic) to start with the prime Galois fields $GF(p)$.  Arithmetic in these fields is simply ordinary addition and multiplication of integers modulo some prime $p$.  For example, in $GF(3)$, there are three numbers ($0$, $1$ and $2$) with the following addition and multiplication rules (and their commutative variants):

$$\begin{aligned}
0 + 0 &amp;= 0 &amp; 1 + 1 &amp;= 2 &amp; 0 \times 0 &amp;= 0 &amp; 1 \times 1 &amp;= 1 \\
0 + 1 &amp;= 1 &amp; 1 + 2 &amp;= 0 &amp; 0 \times 1 &amp;= 0 &amp; 1 \times 2 &amp;= 2 \\
0 + 2 &amp;= 2 &amp; 2 + 2 &amp;= 1 &amp; 0 \times 2 &amp;= 0 &amp; 2 \times 2 &amp;= 1 \\
\end{aligned}$$

The only unusual rules here are $1 + 2 = 0$, $2 + 2 = 1$ and $2 \times 2 = 1$; those are the cases where, in normal arithmetic, the result would've been equal to or greater than $3$, so it's "wrapped around" by subtracting $3$.  From these rules, we can also determine the inverses.  It turns out that $-0 = 0$, $-1 = 2$ and $-2 = 1$ (since $1 + 2 = 0$) and $1/1 = 1$ and $1/2 = 2$ (since $2 \times 2 = 1$), so they indeed do exist and belong to the field.  (I'll leave verifying that the inverses are all unique, and that these rules indeed also satisfy all the other field axioms, as an exercise.)

Why do we require $p$ to be prime, then?  Well, it turns out that if a number $m$ is not prime, then some numbers won't have multiplicative inverses modulo $m$:  for example, there is no integer $a$ such that $2 \times a = 1 \pmod 4$.  Thus, the integers modulo $m$ don't actually form a field (but only a ring) unless $m$ is prime.

However, if $m$ is a prime power &mdash; i.e. a number of the form $m = p^n$, for some prime $p$ and some positive integer $n$ &mdash; then we can still save things by changing the rules on how addition and multiplication work.  This is where all that stuff about the vectors and polynomials comes in.  However, what you should keep in mind is that they don't really represent any added complexity, just alternative ways of looking at things.  Fundamentally, we're still dealing with a set of $p^n$ numbers and some arithmetic operations defined on them &mdash; it just turns out that, for example, the multiplication rule we'll need to use is pretty easy to describe if we identify each number in the field with a polynomial, at least if you still remember the rules for adding and multiplying (and dividing) polynomials that you may have also learned in high school.

So, let's start with vectors and addition.  Given a number $a \in \{0, \dotsc, p^n-1\}$, we can represent it in a natural way with $n$ base-$p$ digits $a_0, \dotsc, a_{n-1}$, such that $$a = a_0 + a_1 p + a_2 p^2 + \dotsb + a_{n-1} p^{n-1}.$$

This is exactly how you'd represent a binary number modulo $2^n$ as a string of $n$ bits.  We could also call the string a vector, since that's basically what a vector is: a finite-length sequence of numbers.

Now, when you normally add numbers together digit by digit, you need to keep track of carries.  On the other hand, when you add two vectors together, it's simpler: you just add up the corresponding numbers in each vector separately.  Now, it just turns out that the addition rule we'll need to use, to make the field axioms work in a field with $p^n$ elements, is exactly this "carryless addition".  For example, in $GF(4)$ (which we often write as $GF(2^2)$ to emphasize that $4 = 2^2$ is indeed a prime power) the addition rules look like this:

$$\begin{aligned}
0 + 0 &amp;= 0 &amp; 0 + 2 &amp;= 2 &amp; 1 + 1 &amp;= 0 &amp; 1 + 3 &amp;= 2 &amp; 2 + 3 &amp;= 1 \\
0 + 1 &amp;= 1 &amp; 0 + 3 &amp;= 3 &amp; 1 + 2 &amp;= 3 &amp; 2 + 2 &amp;= 0 &amp; 3 + 3 &amp;= 0 \\
\end{aligned}$$

They look a lot more logical if you write them out in binary:

$$\begin{aligned}
00 + 00 &amp;= 00 &amp; 00 + 10 &amp;= 10 &amp; 01 + 01 &amp;= 00 &amp; 01 + 11 &amp;= 10 &amp; 10 + 11 &amp;= 01 \\
00 + 01 &amp;= 01 &amp; 00 + 11 &amp;= 11 &amp; 01 + 10 &amp;= 11 &amp; 10 + 10 &amp;= 00 &amp; 11 + 11 &amp;= 00 \\
\end{aligned}$$

Here you can see that we're just adding up the digits modulo $2$ and ignoring any carries.  You might also recognize this "addition" rule as the same operation as bitwise XOR.  This is not unique to $GF(4)$; the elements of $GF(2^n)$ for any $n$ can be represented as $n$-bit bitstrings, and their addition as bitwise XOR.

So, now we know how to add numbers in $GF(p^n)$.  What about multiplication, then?  Well, this is where the polynomials come in.  You see, one way to describe the multiplication rule is to imagine that the digits $a_0, \dotsc, a_{n-1}$ of the number $a$ are the coefficients of a polynomial $$a[x] = a_0 + a_1 x + a_2 x^2 + \dotsb + a_{n-1} x^{n-1}$$ with the unknown $x$.  (Here, the variable $x$ is purely a formal placeholder; we'll never assign it a value, so you'll never have to worry about "what's $x$?".  It's just there so that we can use the high school algebra rules for manipulating polynomials in $x$.)

Then, to multiply two numbers $a$ and $b$, we just take their respective polynomials $a[x]$ and $b[x]$, multiply them together using the high school algebra rules (doing all the internal arithmetic modulo $p$), and take the coefficients of the result.  This is all pretty simple: remember that polynomial multiplication is also pretty straightforward, being just like normal digit-by-digit multiplication except that, again, there are no carries.

But wait!  Won't the multiplication sometimes give me terms of order $x^n$ or higher?  If I include them in the digit string, wouldn't that result in a number larger than $p^n-1$?

Well, yes.  That's why there's another step: after the multiplication, we need to reduce the result modulo a suitable polynomial (specifically, an irreducible monic polynomial of order $n$).  That is to say, we take the result of the multiplication and divide it by this reducing polynomial (which we can again do with high school polynomial long division), again remembering to do all arithmetic on the coefficients modulo $p$, and keep the remainder (which will be of order $x^{n-1}$ or less).  Of course, in practice it's usually more efficient to do the reduction during the multiplication, so that you don't need to store lengthy intermediate results.

OK, so where does that reducing polynomial come from?  Well, it turns out that we have some latitude in choosing it, since there are usually several polynomials that will work.  Each of them will give a different multiplication rule, although all the fields so constructed (and, more generally, all finite fields with $p^n$ elements) are isomorphic, in the sense that, for any two Galois fields $A$ and $B$ of $p^n$ elements, there's an invertible function $f: A \to B$ mapping one field to the other so that $f(a + b) = f(a) + f(b)$ and $f(a \times_A b) = f(a) \times_B f(b)$, where $\times_A$ and $\times_B$ denote the multiplication operators of the two fields.  Thus, when we only care about the general algebraic properties of the field, and not about the specific representation of the numbers, it's common to speak of "the" Galois field of order $p^n$, even though it might have multiple representations.

If you're asked to calculate something in a specific Galois field, the reducing polynomial will normally be given for you.  For example, if you're writing an AES implementation, it uses $GF(2^8)$ with the reducing polynomial $x^8 + x^4 + x^3 + x + 1$ (where, since $p=2$, all coefficients are either $0$ or $1$).

If you get to choose your own representation, and thus your own reducing polynomial, you should generally try to pick something that makes the calculations easy, subject to the irreducibility constraints stated above.  Often this means picking something with as few non-zero coefficients as possible, and with all those coefficients occurring on low-order terms (except for the $x^n$ term, which must have a coefficient of $1$ for the polynomial to be monic and of order $n$, of course).

I could go into more detail on how to implement multiplication in binary Galois fields $GF(2^n)$, since what I've written above is still on a rather abstract level, and since &mdash; especially to someone coming from a programming background &mdash; the theory is often more complicated than the actual code (or at least looks that way).  However, to be honest, I'm more familiar with the theoretical side of things myself, and in any case this answer is already more than long enough.  Wikipedia does have a nice article on finite field arithmetic that you could start with, though.

Oh, and what about Galois fields that are not of order $p^n$ for some prime $p$ and positive integer $n$?  Well, it turns out that there aren't any &mdash; you just can't satisfy the field axioms if the number of elements has two distinct prime factors.  So, alas, there's no such thing as $GF(6)$ or $GF(10)$.