Fields

Algebraic structure on which basic math can be performed.

Algebraic closure of field is an algebraic extension of that is algebraically closed. For example: fundamental theorem of algebra states that algebraic closure of field of real numbers is field of complex numbers.

Algebraic extension of a field refers to a field such that every element is a root to a non-zero polynomial with coefficients in , in other words, every element of field is algebraic over small field.

A field is algebraically closed if every non-constant polynomial has a root in .

Properties

  • Abelian group under addition
  • Non-zero numbers form abelian group under multiplication
  • multiplicative distribution over addition

Finite Fields (Galois Fields)

Fields defined on a number and the result is in the set.

  1. Closed
  2. Associative:
  3. Identity:
  4. Inverse:
  5. Commutative

It has elements in it, where p = prime, and m is an integer.

are defined as the finite fields with notation:

  1. m = 1: prime fields
  2. m > 1: extension fields

Image.jpeg

Note: are defined as finite fields without 0 as it doesn’t have an inverse.

Prime fields can be defined on any integer and include number from 0 till that number. All of the operations are done modulo that number.

Example: is a field defined on prime number 5 and include these numbers.

Extension fields are polynomials and take the form:

Example: ‘s elements are

(a2, a1, a0)
(0, 0, 0) = 0
(0, 0, 1) = 1
(0, 1, 0) = x
(1, 0, 0) = x²
(0, 1, 1) = x+1
(1, 1, 0) = x²+x
(1, 0, 1) = x²+1
(1, 1, 1) = x²+x+1

Properties

  • Every element of a GF(q) are roots of the polynomial . Generally, every element in GF(p^n) satisfies the polynomial equation .
  • every field has a characteristic which is p for which np=0 and is used to find identity of the field.
  • Non-zero elements of a finite field form a multiplicative cyclic subgroup. This means, all non-zero elements can be expressed as powers of a single element. This element is called primitive element.
  • All fields generated in GF(q) are isomorphic.

Roots of Unity in Finite Fields

  1. Every non-zero element of is a root of unity.
  2. Def: Primitive RoU: , but .
  3. has a nth primitive RoU iff n divides q-1.

Quadratic Residue

If and are co-prime, then is called quadratic residue modulo m if has a solution. Vice Versa, is called quadratic non-residue if it does not have a solution.

Total quadratic residues of a prime , excluding 0, if p is odd, and , if p is even.

Legendre Symbol

Easier notation used to denote the relationship between and . Can be easily encoded in a functional form to be used in cryptographic operations.

Let and be integers, and ,

Extension Fields

Adicity

Something which is referenced very often when creating various fields for proving systems is the 2-adicity of the field.

Adicity refers to the largest size of the subgroup that can be formed in the field. All the other subgroups are smaller than the largest subgroup and thus, to create snarks that can prove large computation, it is required to take fields with high 2-adicity value.

Interesting fields

Field element is the most granular entity in a SNARK which require operations like MSM, NTT to perform actions on a polynomial. Many interesting fields have been invented to perform efficient arithmetic inside the field.

Goldilocks

+1 in the modulus means that field will have high 2-powers root of unity which are used in computing large NTTs in SNARKs. Originally, introduced in Ham15 which satisfied golden ratio: , -1 meant not having high 2-adicity, thus was modified to by Plonky2 team.

Pros:

Cons:

  • non-native arithmetic can’t be emulated efficiently

Baby Bear

Mersenne

References