refer 4.3

In AES, Galois field arithmetic is used in most layers, especially in the S-Box and theMixColumn layer.

In order to have all four basic arithmetic operations (i.e., addition, subtraction, multiplication, division) in one structure, we need a set which contains an additive and a multiplicative group. This is what we call a field.

## Definition 4.3.2 Field

A field F is a set of elements with the following properties:

### 加法结构：加群===Abelian Group

All elements of F form an additive group with the group operation “+” and the neutral element 0.

• Closure
• Associative
• Inverse Exist
• Commutative

All elements of F except 0 form a multiplicative group with the group operation “×” and the neutral element 1.

• Closure

• Associative

• Multiplicative Identity Exist

∀ x ∈ F\{0}, ∃ x-1∈ F, s.t. x◦x-1=x-1◦x=i

通过分配律可以证明，

a(b+c) = (ab)+(ac)，让c=0

a(b+0) = (ab)+(a0) => ab = ab + a0 两边加上ab的加法逆 -ab => a0=0，再通过满足交换律得到0a=0，

所以0跟任何元素相乘都是0，都不会是multiplicative identity，所以0不存在乘法逆

• Commutative

• Distributivity

When the two group operations are mixed, the 分配律 distributivity law holds, i.e., for all a,b,c ∈ F: a(b+c) = (ab)+(ac).

Note: Field is a non-zero communitive ring+Inverse Exist(except additive Identity），实际上zero communitive ring {0} 也满足上面的properties

The set R of real numbers is a field with the neutral element 0 for the additive group and the neutral element 1 for the multiplicative group. Every real number a has an additive inverse, namely −a, and every nonzero element a has a multiplicative inverse 1/a.

https://en.wikipedia.org/wiki/Field_(mathematics)#Constructing_fields_from_rings

## Finite Field

https://en.wikipedia.org/wiki/Finite_field

 Fields with a finite number of elements, which we call finite fields or Galois fields. The number of elements in the field is called the order 阶 or cardinality of the field. Roughly speaking, a Galois field is a finite set of elements in which we can add, subtract, multiply and invert. 有限域乘法 加法结构

1．有限域的乘法结构 

https://math.stackexchange.com/questions/837562/why-is-the-multiplicative-group-of-a-finite-field-cyclic

2．有限域的加法结构 

## Characteristic of a Field

Field is a non-zero communitive ring，根据Field定义属性，

multiplicative identity normally denoted as 1 ∈ F, what you have to ask to work out the characteristic of a Field Ch(F) is what is the smallest number of times I have to add 1 to itself to get back 0:

1+1+…………..+1 = 0

there is a little caveat to this what if you can add one to itself as many times as you like and never get 0 back again, for example take rational numbers Q which is a filed, you can add 1 to itself as many times as you like and you’ll get a bigger and bigger rational but you’ll never come back to 0, so you might expect the Ch(F) to be infinity but it isn’t, the way we define the characteristic of a field where you can add up 1 to itself arbitrarily many times and never get 0 back again is we define it to be zero, so the characteristic of Rational number Ch(Q) is defined to be zero

Prime Field F2 = { 0, 1 } 1+1=0, ch(F2)=2

n∈N, n*1 = 1+1….+1 (n times)

m,n∈N, n*1+m*1 = (n+m)*1

(n*1)*(m*1) = (n*m)*1

the characteristic of any field is either 0 or a prime number. A field of non-zero characteristic is called a field of finite characteristic or positive characteristic or prime characteristic.

Characteristic of a Field Ch(F) can only be zero or prime, ch(F)= 0 or prime(2,3,5….)

Prove: assume Ch(F) = n = ab (non of a or b is 1)

according to the definition, n*1=0 => (ab)*1 = 0 => (a*1)*(b*1) = 0 implies that a*1 =0 or b*1=0,

for example, if a*1=0 because n = ab (non of a or b is 1) implies that a<n,b<n, means that we have found a smaller number a that times 1 equal to 0, this contradict to the definition of n is the characteristic of the field(the smallest )

If the characteristic were p’, a composite, say p’=pn′, then 0=pn′. This shows p is a zero-divisor and therefore not a unit.

If p were a unit, you would have 0=p−1⋅0=p−1pn′=n′

example:

Fp=Z/(pZ) = { 0¯, 1¯, 2¯,(p-1)¯ }, Ch(Fp) = p , why?

1¯+1¯= 2¯

1¯+1¯+1¯=3¯

p*1¯ = 1¯+1¯+…+1¯ (p times) =p¯ = 0¯

Real number: Ch(R) = 0

Rational number: Ch(Q) = 0

Complex number: Ch(C)=0

### Theorem 4.3.1 prime power

A field with order m only exists if m is a prime power, i.e., m = pn, for some positive integer n and prime integer p. p is called the characteristic 特征 of the finite field.

n=1 => Prime Fields

n>1 => Non-Prime Fields

Prime fields vs non-prime fields https://crypto.stackexchange.com/questions/78422/prime-fields-vs-non-prime-fields

Example:

This theorem implies that there are, for instance, finite fields with 11 elements(11=111, or with 81 elements (since 81 = 34) or with 256 elements (since 256 = 28, and 2 is a prime). However, there is no finite field with 12 elements since 12 = 22 · 3, and 12 is thus not a prime power.

https://www.quora.com/Why-must-a-finite-field-have-prime-power-order

Note that the order of the field must be a power of a prime, which is the characteristic (additive order) of every non-zero element. Short answer, because it’s finite, and because it’s a field. I know, that sounds ridiculous, but pretty much that’s all the proof uses. What we prove is that any finite field is “a vector space over a subfield of prime order”.

The field has a multiplicative identity, 1, and an additive identity, 0. Since the field is finite then there is a minimal number N such that 1+1+…+1=0 for N ones. Suppose N were composite. Then we could find two integers greater than 1, such that pq=N, and then there are two elements of the field 1+1+…+1, one with p 1’s, and one with q. Those two elements are not 0, since p,q<N. Their product is 0, which cannot be true in a field. (This is called the “scalar field”. It’s a subfield, isomorphic to integers modulo N). So N must be prime. From there it’s a quick application of the distributive law to show the additive order of every non-zero element in the field must be N, a prime.

Finally, you inductively construct the elements of the field in the form a0⋅1+a1x1+a2x2+…, for ai∈0…p−1. (After k steps you have found an additive subgroup of the field with pk elements. If this is not every element in the field, simply take another element of the field as xk. The only detail you need to make this proof rigorous is to prove that the elements so generated are distinct, which is not difficult.)

example: Let’s try it with a composite number, 12. We have 3⋅4 mod 12 =0, so

0=3−1⋅0=3−1⋅(3⋅4)=(3−1⋅3)⋅4=1⋅4=4.

That’s why it does not work with composite numbers. Why it does work with prime numbers is a more substantial thing: How do you prove everything except 0 has a multiplicative inverse in that case? That involves the quotients in Euclid’s algorithm.

https://math.stackexchange.com/questions/633056/the-proof-that-a-finite-field-has-a-prime-power-order#:~:text=As%20the%20field%20is%20finite,field%20has%20order%20pn.

## Prime Fields

### 例子1：Prime Fields GF(p)

The most intuitive examples of finite fields are fields of prime order, i.e., fields with n=1. Elements of the field GF(p) can be represented by integers 0,1, . . . , p−1. The two operations of the field are modular integer addition and integer multiplication modulo p.

Theorem 4.3.2

Let p be a prime. The integer ring Zp is denoted as GF(p) and is referred to as a prime field, or as a Galois field(or Finite Fields) with a prime number of elements. All nonzero elements of GF(p) have an inverse. Arithmetic in GF(p) is done modulo p.

example1:

A very important prime field is GF(2), which is the smallest finite field that exists. Let’s have a look at the multiplication and addition tables for the field. Example 4.4. Let’s consider the small finite field GF(2)={0,1}. Arithmetic is simply done modulo 2, yielding the following arithmetic tables: addition

| + | 0 | 1 | | —- | —- | —- | | 0 | 0 | 1 | | 1 | 1 | 0 | multiplication

× 0 1
0 0 0
1 0 1

GF(2) addition, i.e., modulo 2 addition, is equivalent to an XOR gate. What we learn from the example above is that GF(2) multiplication is equivalent to the logical AND gate. The field GF(2) is important for AES.

example 2：

We consider the finite field GF(5) = {0,1,2,3,4}. The tables below describe how to add and multiply any two elements, as well as the additive and multiplicative inverse of the field elements. Using these tables, we can perform all calculations in this field without using modular reduction explicitly.

−0 = 0 −1 = 4 −2 = 3 −3 = 2 −4 = 1

+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3

multiplicative inverse: 1−1 = 1 2−1 = 3 3−1 = 2 4−1 = 4

x 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

### 例子2：构造Prime Fields Z/(pZ)

Z = {0,1, -1, 2, -2, . . .}

 Fp , p = 2, 3, 5, 7 ,11, 13, ….. Fp = p

Z/(pZ)

 pZ={np n∈Z} = {0, p, -p, 2p, -2p,………}

Z是Abelian group

pZ = {0, p, -p, 2p, -2p,………}, denoted by 0¯

1+pZ = {1, 1+p, 1-p,1+ 2p, 1-2p,………}, denoted by 1¯

2+pZ = {2, 2+p, 2-p,2+ 2p, 2-2p,………}, denoted by 2¯

p-1+pZ = {p-1, 2p-1, -1,3p-1, -p-1,………}, denoted by (p-1)¯

Z/(pZ) = { 0¯, 1¯, 2¯,(p-1)¯ } 刚好prime order p

a¯+b¯=(a+b)¯ 前面在group章节中证明过，现在要证明其满足fileds的加法结构即加法结构下是Abelian group：

1）closure，根据定义很明显 ∀ a¯,b¯ ∈ Z/(pZ), a¯+b¯=(a+b)¯ ∈ Z/(pZ)

2）associativity, (a¯+b¯)+c¯ =a¯+ (b¯+c¯)

(a¯+b¯)+c¯ = (a+b)¯ + c¯ = ((a+b)+c)¯

a¯+ (b¯+c¯) = (a+(b+c))¯, (a+b)+c= a+(b+c) 得证

3）identity

a¯+ 0¯ = (a+0)¯ =a¯

0¯ +a¯ = a¯

4) inverse

∀ a¯ ∈ Z/(pZ)

a¯ + (-a+p)¯ = (a-a+p)¯=p¯=0¯

5) communitativity

a¯+b¯ = (a+b)¯

b¯+a¯ = (b+a)¯ = (a+b)¯ =a¯+b¯

Multiplication Composition Law

a¯b¯ = (ab)¯

for a¯,b¯ ∈ Z/(pZ), take arbitrary elements from a¯,b¯: a+z1p and b+z2p

a¯b¯ =((a+z1p)(b+z2p))¯=(ab+az2p+z1pb+z1pz2p)¯

a,b,p,z1,z2都是integer，所以根据commutativity以及associativity of multiplication for integer

ab+az2p+z1pb+z1pz2p = ab+az2p+z1bp+z1pz2p = ab+(az2+z1b+z1pz2)p

az2+z1b+z1pz2 必然是integer，即 az2+z1b+z1pz∈ Z，所以(az2+z1b+z1pz2)p ∈ pZ，所以ab+(az2+z1b+z1pz2)p ∈ (ab)¯

1）closure，根据定义很明显 ∀ a¯,b¯ ∈ Z/(pZ), a¯b¯=(ab)¯ ∈ Z/(pZ)

2）associativity, (a¯b¯)c¯ =((ab)c)¯ =a¯(b¯c¯) =(a(bc))¯

3）identity

1¯a¯=(1a)¯=a¯ = a¯1¯

4) inverse

∀ a¯ ∈ F\{0¯}=Z/(pZ)\{0¯} = { 1¯, 2¯,(p-1)¯ }={},

∃ a¯-1∈F\{0¯}, s.t. a¯◦a¯-1=a¯-1◦a¯=1¯ or ∃ b¯∈ F\{0¯}, s.t. a¯◦b¯=b¯◦a¯=1¯

first, prove a¯◦b¯<>0¯, if a¯◦b¯ = 0¯, means a¯◦b¯=zP =>ab=zp , so that the prime factor of a or b must contain p, but

a¯,b¯ ∈ { 1¯, 2¯,(p-1)¯ } so the max of a,b is (p-1) < p 得证a¯◦b¯<>0¯

second, prove for different b1,b2, a¯◦b1¯<>a¯◦b2¯, assume a¯◦b1¯= a¯◦b2¯, => (a◦b1)¯= (a◦b2)¯, means a◦b1 and a◦b2 in the same cosets, a◦b1=a◦b2+zp => a◦b1-a◦b2=zp => a(b1-b2) = zp ，跟前面一样the max of a,b1,b2 is (p-1) < p

finally,

b¯ ∈ { 1¯, 2¯,(p-1)¯ } 有 p-1种可能，然后每种可能跟a¯ 的 a¯◦b¯结果都是不同的，a¯◦b¯=(a◦b)¯∈ { 0¯, 1¯, 2¯,(p-1)¯ } 但是前面知道了a¯◦b¯<>0¯，所以自然的必然存在一个b¯使得 a¯◦b¯=1¯

5) communitativity

a¯b¯=(ab)¯ = b¯a¯=(ba)¯

6) distributivity

a¯(b¯+c¯) = a¯b¯+a¯c¯

a¯(b¯+c¯) = a¯(b+c)¯ = (a(b+c))¯

a¯b¯+a¯c¯ = (ab)¯+(ac)¯=(ab+ac)¯

a(b+c)=ab+ac => (a(b+c))¯= (ab+ac)¯ 得证

## Field Extensions

K / F , K Over F vector space

AES: primitive polynomia 本原多项式