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 was watching this class about AES in this LINK and I was trying to grasp the concept of prime fields, which is a finite field with prime order $p$.
The non-prime field part (order is $p^n$) is where it gets harder for me. The teacher jumps into "extension fields", and does not explain the link between it and non-prime fields. Also, he just affirms that elements of $GF(p)$ are integers, while elements of $GF(p^n)$ are polynomials.
Why the difference between the two?
elements of $GF(p)$ are integers, while elements of $GF(p^n)$ are polynomials.
Why the difference?
TL;DR: because integers modulo $p^n$ do not form a field.
Here's a pragmatic construction of $GF(p^n)$ useful for applied cryptography, including AES which uses the field $GF(2^8)$ extensively.
$GF(p)$ for prime $p$ is the field of arithmetic modulo $m$ for modulus $m=p$. Arithmetic modulo an integer $m$ works as integer arithmetic except that all results are reduced to the range $[0,m)$ by subtraction of $q\,m$ for some appropriate integer $q$. Arithmetic modulo $m$ keeps the usual properties of addition and multiplication: their are internal laws with associativity, commutativity, distributivity, neutral $0$ for addition and $1$ for multiplication, existence of an opposite (w.r.t. addition) for all elements. And, specifically when $m$ is prime, arithmetic modulo $m$ gains a property of rationals and reals that integers do not have: existence of an inverse/reciprocal (w.r.t. multiplication) for all elements except $0$. That additional property makes arithmetic modulo $p$ a field of $p$ elements, when arithmetic modulo a composite $m$ is not¹.
When we want to make a field of $m$ elements and $m$ is not prime, we thus can't use arithmetic modulo $m$. It turns out that there is an alternative construction if and only if $m$ is of the form $p^n$ with $p$ prime. That's $GF(p^n)$.
One way to think an element $A$ of $GF(p^n)$ is as a vector $(a_0,a_1,\ldots,a_{n-1})$ of $n$ elements $a_i\in GF(p)$. At least that gives us the right count of elements $p^n$, and we can define a well-behaved addition as $$A+B=(a_0+b_0\bmod p,a_1+b_1\bmod p,\ldots,a_{n-1}+b_{n-1}\bmod p)$$ with the all-zero vector the neutral. But somewhat we need to define multiplication in such a way that $A\,B$ is also a vector of $n$ elements in $GF(p)$, and all except one elements have an inverse².
That's where polynomials come to the rescue. We assimilate $A=(a_0,a_1,\ldots,a_{n-1})$ to the (univariate) polynomial $a_0+a_1\,x^1+\ldots+a_{n-1}\,x^{n-1}$ of degree less than $n$ and coefficients $a_i\in GF(p)$. Notice that the rules of addition of polynomials with coefficients in $GF(p)$ coincide with our earlier definition of addition.
Now we pick a polynomial $M=m_0+m_1\,x^1+\ldots+m_{n-1}\,x^{n-1}+m_n\,x^n$ of degree³ $n$ with coefficients $m_i\in GF(p)$, and define the product $A\,B$ in our would-be field as $$\underbrace{A\,B}_{\text{in would-be field}}=C=\underbrace{A\,B\bmod M}_{{\text{in polynomials with}\\\text{coefficients in }GF(p)}}$$ The right side means that $C$ is the⁴ polynomial with coefficients $c_i\in GF(p)$, of degree less than the degree of $M$ (hence of degree less than $n$, hence representable as a vector of $n$ elements in $GF(p)$ as desired), such that there exists a polynomial $Q$ with coefficients $q_i\in GF(p)$ with $$0=C+Q\,M-A\,B$$ per the normal rules of addition and multiplication of polynomials with coefficients in $GF(p)$. That is $$0=\sum_{0\le i<n}\left(\left(c_i+\sum_{0\le j<n}\left(q_j\,m_{i-j}-a_j\,b_{i-j}\right)\right)x^i\right)$$ or equivalently when we get back to vector notation rather than polynomials $$\forall i\in[0,n),\ \underbrace{0=c_i+\sum_{0\le j<n}\left(q_j\,m_{i-j}-a_j\,b_{i-j}\right)}_{\text{in }GF(p)\text{, that is}\pmod p}$$ We've already seen that this construction of multiplication is an internal law. It's easy to show that it inherits from the field of arithmetic in polynomials with coefficients in $GF(p)$ the properties of associativity, commutativity, distributivity, and neutral the constant polynomial $1$, that is the vector $(1,0,\ldots,0)$. We have constructed a commutative ring with $p^n$ elements.
It can be shown that if (and only if) polynomial $M$ is irreducible, each element has an inverse, which completes the field properties. And it can be shown that there exits an isomorphism among the different fields that we obtain for different irreducible polynomials $M$, which is why mathematicians speak of the field $GF(p^n)$, rather than of the field $GF(p^n)$ obtained for a particular irreducible polynomial $M$, as practical cryptographers often do.
Relation between extension fields and non-prime fields
A field $G$ is an extension field of $F$ when $F$ (or $F'$ with a trivial mapping to $F$) is a subset of $G$ and is a field under the same addition and multiplication laws that make $G$ a field.
When we restrict $GF(p^n)$ constructed as above to the set of constant polynomials (equivalently, the set of vectors of $n$ elements in $GF(p)$ with all expect the first set to zero), we are back to a subset of $p$ elements that matches $GF(p)$.
Otherwise said, $GF(p^n)$ is an extension field of $GF(p)$.
Notes:
¹ Arithmetic modulo a composite $m$ is only a commutative ring of $m$ elements, but not a field. Proof: if $m$ is composite, let $a$ be the smallest prime divisor of $m$. If $a$ had an inverse $x$ modulo $m$, we'd have $a\,x\equiv1\pmod m$, that is $\exists q\in\Bbb Z,\ a\,x=1+q\,m$. We can write $m=a\,b$ for some $b\in\Bbb Z$. Hence $a\,x=1+q\,a\,b$, hence $a\,(x-q\,b)=1$ in the ring of integers, which can't be since $a$ is prime. Hence $a$ has no inverse modulo $m$ when $m$ is composite. Since $a$ is not zero, one of the field requirement is not met.
² That's the hard part. In particular, the construction of the product as $A\,B=(a_0\,b_0\bmod p,a_1\,b_1\bmod p,\ldots,a_{n-1}\,b_{n-1}\bmod p)$ leaves multiple $A$ without an inverse: all those with at least one of their $a_i=0$ in $GF(p)$.
³ That's exactly degree $n$, otherwise said $m_n\ne0$ in $GF(p)$.
⁴ The polynomial $C=A\,B\bmod M$ is uniquely defined by the relation $0=C+Q\,M-A\,B$. That $C$ can be (and in practice often is) obtained by computing the product $A\,B$ as a polynomial with coefficients in $GF(p)$ of degree less than $2\,n-1$, and progressively reducing that product's degree from at most $n+j$ to less than $n+j$, by computing $q_j$ and subtracting $q_j\,x^j\,M$, with $q_j=d_{n+j}/m_n$ computed in $GF(p^n)$, and $d_{n+j}$ is the high-order coefficient of the progressively reduced product. To simplify that computation, it is customarily used $m_n=1$, that is $M$ a monic polynomial.
