Rings, Fields notes

Rings

a ring over the set

$\mathbb{R}$ is given as

$(\mathbb{R},+,\cdot )$, which has two binary operations, denoted by

$+$ and

$\cdot$ such that:

1. $\mathbb{R}$ is an abelian group (commutative group) with respect to +.
2. $\cdot$ is associative. i.e.,
   $(a\cdot b)\cdot c=a\cdot (b\cdot c)$ for all
   $a,b,c\in \mathbb{R}$.
3. The distributive laws hold. i.e., for all
   $a,b,c\in \mathbb{R}$ we have
   $a\cdot (b+c)=(a\cdot b+b\cdot c$ and
   $(b+c)\cdot a=b\cdot a+c\cdot a$.

We use

$0$ (the zero element) to denote the identity element of the abelian group

$\mathbb{R}$ with respect to addition.
The additive inverse of

$a$ is denoted by

$-a$, also

$a+(-b)$ is abbreviated by

$a-b$.

Definition

1. A ring is called a ring with identity if the ring has a multiplicative identity—that is, if there is an element e such that
   $ae=ea=a$ for all
   $ae\mathbb{R}$.
2. A ring is called commutative if
   $\cdot$ is commutative.
3. A ring is called an integral domain if it is a commutative ring with identity
   $e\ne 0$ in which
   $ab=0$ implies
   $a=0$ or
   $b=0$.
4. A ring is called a division ring (or skew field) if the nonzero elements of
   $\mathbb{R}$ form a group under
   $\cdot$.
5. A commutative division ring is called a field

Polynomials

from elementary algebra, a polynomial is regarded as an expression of the form

$$\begin{array}{r}{a}_0+a_{1}x+\cdots +a_n{x}^n\end{array}$$

the

$a$'s are called the coefficients and are usually real or complex numbers.

$x$ is viewed as a variable. The arithmetic of polynomials is governed by familiar rules. The concept of polynomial and the associated operations can be generalized to a formal algebraic setting in a straightforward manner.

Let

$R$ be an arbitary ring. A polynomial over

$R$ is an expression of the form

$$\begin{array}{r}f(x)=\sum _{i=0}^n{a}_i{x}^i=a_0+a_{1}x+\cdots +a_n{x}^n,\end{array}$$

where

$n$ is a nonegative integer, the coefficients

$a_i,0\le i\le n$, are elements of

$R$, and

$x$ is a symbol not belonging to

$R$ called an indeterminate over

$R$.

Prime fields

Let

$p\in \mathbb{P}$ be a prime number and

$({\mathbb{Z}}_p,+,\cdot )$ be the ring of modular

$p$ arithmetic. To differentiate between arbitary modular arithmetic rings we write a prime fields of characteristic

$p$ as

$({\mathbb{F}}_p,+,\cdot )$

An impotant proterty of prime fields is that any prime field of charateristic

$p$ has exactly

$p$ elements which can be represented on a computer with not more than

$lo{g}_2(p)$ bits. This is in contracts to fields which may be require an unbounded amount of bits to properly describe an arbitary precession representation.

Prime fields are special case of modular arithmetic rings. Addition and multiplication can be computed by first doing integer addition and multiplication, and then considering the remainder in Euclidean division by

$p$ as the result.

As above, (in Rings), for any prime fields element

$x\in {\mathbb{F}}_p$, its additive inverse (the negative) is given by

$-x=p-x\text{mod }p$.

For

$x\ne 0$, the multiplicative inverse always exists, and is given by

$x^{-1}=x^{p-2}$

Division is then defined by multiplication with the multiplicative inverse;

$\frac{a}{b}=b\cdot a^{-1}$

NOTE:
In modular

$n$ arithmetic, a number

$r$ has a multiplicative inverse if and only if

$n$ and

$r$ are coprime. Since

$gcd(n,r)=1$ in that case, we know from the Extended Euclidean Algorithm that there are numbers

$s$ and

$t$, such that the following equation holds:

$1=s\cdot n+t\cdot r$
If we take the modulus n on both sides, the term

$s\cdot n$ vanishes, which tells us that

$t\text{mod}n$ is the multiplicative inverse of

$r$ in modular

$n$ arithmetic.

See: Extended Euclidean Algorithm

Extended field

Pairing based SNARK systems are crucially dependent on certain types of pairings defind on elliptic curves over prime field extensions.

Given some prime number

$p\in \mathbb{P}$, a natural number

$m\in \mathbb{N}$, and a irreducible polynomial

$P\in {\mathbb{F}}_p[x]$ of degree

$k$ whith coefficients from the prime field

${\mathbb{F}}_p$, a prime extension

$({\mathbb{F}}_{p^k},+,\cdot )$ is defined as follows

The set

${\mathbb{F}}_{p^k}$ of the prime field extension is given by the set of all polynomials with a degree less than

$k$:

$$\begin{array}{r}{\mathbb{F}}_{p^k}:=\{a_{k-1}{x}^{k-1}+a_{k-2}{x}^{k-2}+\cdots +a_1{x}^1+a_0|a_i\in {\mathbb{F}}_p\}\end{array}$$

The addition law of the prime field extension

${\mathbb{F}}_{p^k}$ is given by the usual addition of polynomials:

Let

$\sum _{j=0}^{m_1}{a}_n{x}^n$ and

$\sum _{j=0}^{m_2}{b}_n{x}^n$ be two polynomials from

$R[x]$.

$$\begin{array}{r}+:{\mathbb{F}}_{p^k}\times {\mathbb{F}}_{p^k}\to {\mathbb{F}}_{p^k},(\sum _{j=0}^m{a}_j{x}^j,\sum _{j=0}^m{b}_j{x}^j)\mapsto \sum _{j=0}^m(a_j+b_j)x^j\end{array}$$

The multiplication law of the prime field extension

${\mathbb{F}}_{p^k}$ is given by first multiplying the two polynomials

$$\begin{array}{r}\times :{\mathbb{F}}_{p^k}\times {\mathbb{F}}_{p^k}\to {\mathbb{F}}_{p^k},(\sum _{j=0}^m{a}_j{x}^j,\sum _{j=0}^m{b}_j{x}^j)\mapsto \sum _{n=0}^{2m}\sum _{i=0}^n(a_i{b}_{n-i})x^n\text{mod}P\end{array}$$

The neutral element of the additive group

$({\mathbb{F}}_{p^k},+)$ is given by the zero polynomial 0.

---

Example:
For a field

${\mathbb{F}}_p$, an extension field is of the form

${\mathbb{F}}_{p^k}$.

An example is to study a binary extension field

${\mathbb{F}}_{p^k}$ where

$p=2$.

In this example,

${\mathbb{F}}_{2^k}$ has its elements represented a polynomials over the base field

${\mathbb{F}}_2$. A polynomial in

${\mathbb{F}}_2$ is an expression where the coefficients come from the set

$\{0,1\}$, and arithemetic operations are performed modulo 2.

The degree of the polynomial will be less than of equal to

$k-1$.
Taking

$k=3$, we can construct extension field

${\mathbb{F}}_{2^3}$ by considering the polynomials of degree 2 over

${\mathbb{F}}_2$.
A primitive polynomial for

${\mathbb{F}}_{2^3}$ would be

$f(x)=x^2+x+1$.

The elements are:

$k$ –> element in

${\mathbb{F}}_{2^3}$
0,0,0 –>

$0$ which is also the additive identity.
0,0,1 –>

$1$ which is also a multiplicative identity.
0,1,0 –>

$x$
0,1,1 –>

$x+1$
1,0,0 –>

$x^2$
1,0,1 –>

$x^2+1$
1,1,0 –>

$x^2+x$
1,1,1 –>

$x^2+x+1$

addition and multiplication are performed modulo 2.

Elliptic curve over prime field:

For a prime power

$p>3$ and

$a,b\in {\mathbb{F}}_p$ (where

$4a^3+27b^2\ne 0$ a.k.a the degenerate case) let

$$\begin{array}{r}E({\mathbb{F}}_p)=\{(x,y)\in {\mathbb{F}}_p\times {\mathbb{F}}_p\text{such that }{y}^2=x^3+ax+b\}\end{array}$$

Pairings

within the development of SNARKs the use pairing-maps on commutative groups is a frequently used. A pairing map if a function that takes pairs of elements from the source field(s)

${\mathbb{G}}_1$ and

${\mathbb{G}}_2$, and maps then to elements in a target field

${\mathbb{G}}_T$ such that the blinearity property holds. i.e.,

Definition:

$e(\cdot ,\cdot ):{\mathbb{G}}_1\times {\mathbb{G}}_2\mapsto {\mathbb{G}}_T$

In other words, a pairing

$e:\mathbb{G}\times \mathbb{G}\mapsto G_T$ is a mapping of points in groups to points in another.

Bilinear in the fact that there is two eponents,

$e(g^a,g^b)=e(g,g{)}^{ab}$

$\mathrm{\forall }a,b\in \mathbb{Z},g\in G$

maps generators to generators.

$g$ generates

$G\Rightarrow e(g,g)$ generates

$G_T$

the example (in reference to the above) is that the group

$G$ is an elliptic curve, and the target group

$G_T$ is a finite field.

$G\subseteq E({\mathbb{F}}_p)$,

$G_T\subseteq E({\mathbb{F}}_{p^k})$, where k = 1,2,3,4,6,10,12

Note:

lets take a finite field under an elliptic curve and call this group

$G$ which has

$q$ point in the gorup

$E({\mathbb{F}}_p)=G$

no lets take an extension

$E({\mathbb{F}}_{p^k})[q]$ which can be thought of a elliptic curve over a 2-dimensional set of points.

Tate pairing:

$e(P,Q)=f_p(Q{)}^{(p^k-1)/q}$

the function

$f_p$ is a polynomial defined by the point

$P$, which is a bivariat polynomial whose inputs are the two coordinated of the point

$Q$. i.e., treat the coordinate

$Q$ as

$(x,y)$.

In crypto we dont like to have such 2-dimensional fields, we prefer to use a ring. So we define two groups

$G_1$ and

$G_2$ that are non-degenerate, where

$e:G_1\times G_2=G_T$, this is an asymetric pairing.