Chapter 5 - Algebra

5.1 Introduction

TLDR: This section provides a general overview of algebra, defining it as the study of abstract mathematical structures. It introduces the key concept of algebraic structures, which are sets equipped with operations satisfying specific axioms, and provides several concrete examples. The section emphasizes both the theoretical importance of algebra and its practical applications in Computer Science.

5.1.1 What Algebra is About

Algebra is a powerful branch of mathematics concerned with the study of abstract structures and their fundamental properties. Unlike arithmetic, which primarily deals with specific numbers and calculations, algebra uses symbols and operations to express general relationships and patterns. This abstraction allows us to reason about mathematical objects in a much broader and more powerful way.

Key Features of Algebra:

• Abstraction: Algebra generalizes concepts beyond specific numbers to symbols and operations, enabling broader applicability.
• Structure: It focuses on the underlying structure of mathematical objects, defining relationships and constraints using axioms.
• Generalization: Results derived in algebra often apply to a wide class of mathematical objects sharing the same underlying structure.

5.1.2 Algebraic Structures

An algebraic structure is a set (a collection of distinct objects) combined with one or more operations that satisfy a set of specific rules, called axioms. These axioms formalize the properties of the operations and govern how they behave when applied to elements within the set. Algebraic structures are also often called algebras.

Key Elements of an Algebraic Structure:

• Set (Carrier Set): The collection of objects that the structure is built upon. It could be numbers, functions, matrices, or anything else.
• Operation(s): Rules for combining or manipulating elements of the set. These can be binary operations (taking two elements as input) or unary operations (taking one element as input).
• Axioms: The defining rules of the structure. They must always hold true for the operations on the set. These define the characteristic properties of the structure.

Examples of Key Algebraic Structures:

• Groups: A set with a binary operation, an identity element, and inverses.
• Rings: A set with two binary operations (addition and multiplication) satisfying certain distributive properties.
• Fields: A special type of ring where every non-zero element has a multiplicative inverse.

5.1.3 Some Examples of Algebras

This subsection provides concrete examples to illustrate the concept of algebraic structures.

• Arithmetic: The set of natural numbers $\mathbb{N}=\{0,1,2,3,...\}$ equipped with the operations of addition ($+$) and multiplication ($\cdot$). This, while seemingly simple, has a very complex structure studied in number theory.

• Linear Algebra: The set of vectors in $R^n$, where $R$ is the set of real numbers, equipped with the operations of vector addition and scalar multiplication. This is a specific example of a more general vector space structure.

• Boolean Algebra: The set $\{True,False\}$ (or equivalently, $\{0,1\}$) with the operations of conjunction (AND), disjunction (OR), and negation (NOT). It’s crucial in digital logic design and computer science. This can also be described using the set operations discussed in chapter 3.

• Integers Modulo $n$ (${\mathbb{Z}}_n$): For a given integer $n$, the set $Z_n=\{0,1,2,...,n-1\}$ with the operations of addition and multiplication modulo $n$. This algebra is fundamental to number theory, cryptography, and coding theory. An example is the algebra used in the encryption algorithms, discussed in Chapter 4.

5.2 Monoids and Groups

TLDR: This section delves into the definitions of monoids and groups, two fundamental algebraic structures. It explains the concepts of neutral elements, associativity, and inverses, and showcases a variety of examples. The non-minimality of group axioms is discussed and several well-known examples of these structures are listed.

5.2.1 Neutral Elements

A neutral element (also known as an identity element) with respect to a binary operation * is an element e within a set $S$ that leaves any other element unchanged when combined with it. This means that for all $a\in S$, the following holds:

$e\ast a=a\ast e=a$

• Left Neutral Element: If only $e\ast a=a$ holds, then e is a left neutral element.
• Right Neutral Element: If only $a\ast e=a$ holds, then e is a right neutral element.

Examples:

• In the integers under addition $(\mathbb{Z},+)$, 0 is the neutral element: $0+a=a+0=a$.
• In the integers under multiplication $(\mathbb{Z},\cdot )$, 1 is the neutral element: $1\cdot a=a\cdot 1=a$.
• For a set $A$ and the set of functions from A to itself $(A^A,\circ )$ where $\circ$ indicates composition, the identity function $id(x)=x$ is the neutral element: $id\circ f=f\circ id=f$ for all functions f : A → A.

Uniqueness of Neutral Elements:

A set with a binary operation can have at most one neutral element. This means that if a set contains both a left neutral element and a right neutral element with respect to a particular operation, then the two neutral elements must be equal. So the same element has to be neutral with respect to all elements in a set.

5.2.2 Associativity and Monoids

An operation is associative if the order in which it is performed in a sequence of operations does not affect the result. Formally, a binary operation $\ast$ on a set $S$ is associative if for all $a,b,c\in S$:

$(a\ast b)\ast c=a\ast (b\ast c)$

A monoid is an algebraic structure defined as a set $M$ equipped with a binary operation $\ast$ that is associative and has a neutral element $e$. Formally, a monoid is represented as $(M,\ast ,e)$.

Examples:

• $(\mathbb{Z},\cdot ,1)$: The integers with multiplication and the neutral element 1.
• $(\mathbb{N},+,0)$: The natural numbers with addition and the neutral element 0.
• $(A^A,\circ ,id)$: For a set A and the set of functions from A to itself, where ∘ indicates composition, the set $A^A$ is a monoid with the identity function $id(x)=x$ for all elements of the base set.

5.2.3 Inverses and Groups

An inverse of an element $a$ (with respect to a binary operation $\ast$) is an element $a^{-1}$ such that when they are combined with the operation $\ast$, the result is the neutral element $e$. Formally, a right inverse to an element $a$ is an element $a^{-1}$ such that $a\ast a^{-1}=e$. Similarly, a left inverse to an element $a$ is an element $a^{-1}$ such that $a^{-1}\ast a=e$. An element has an inverse if it’s both a right and left inverse.

A group is an algebraic structure that expands on the definition of the monoid by requiring that all elements have an inverse element. Formally, a group is represented as $(G,\ast ,e)$, where G is a set, * is an associative binary operation, e is the neutral element and every element in G has an inverse with respect to *.

Examples:

• $(\mathbb{Z},+,0)$: The integers with addition as the operation, where the inverse of an integer $a$ is $-a$.
• $(\mathbb{Q}\setminus \{0\},\cdot ,1)$: The set of rational numbers excluding zero, with multiplication as the operation and 1 as the neutral element. The inverse of a rational number $a$ is $\frac{1}{a}$.
• $({\mathbb{Z}}_n,\oplus ,\ominus ,0)$: The integers modulo $n$ with addition modulo $n$ as the operation, the inverse element with respect to addition defined to be $\ominus$ and 0 as neutral element.
• The set of rotations of the unit circle.

5.2.4 (Non-)minimality of the Group Axioms

A set of axioms is minimal if no axiom can be derived from the others. It’s interesting to note that the traditional group axioms aren’t minimal. This means it’s possible to create a smaller set of axioms from which you can still derive all the group’s properties:

1. Associativity: $(a\ast b)\ast c=a\ast (b\ast c)$ for all elements a, b, and c in the group
2. Neutral element: Only the right identity is required. The rule $a\ast e=a$ has to be added. This also implies $e\ast a=a$.
3. Inverse element: Only a right inverse is required. The rule $a\ast a^{-1}=e$ has to be added. This also implies $a^{-1}\ast a=e$.

5.2.5 Some Examples of Groups

• The integers under addition: $(\mathbb{Z},+,-,0)$ The set of integers with the standard addition operation is a group, with 0 as the neutral element and -a as the inverse.
• The positive rational numbers under multiplication: $({\mathbb{Q}}^{+},\cdot {,}^{-1},1)$ The set of positive rational numbers with multiplication, where 1 is the identity element, and $\frac{1}{a}$ is the inverse of a.

5.3 The Structure of Groups

TLDR: This section explores further aspects of group structure, including direct products, homomorphisms, subgroups, the order of group elements and groups themselves, cyclic groups, and Euler’s totient function. It also touches upon the application of group theory in the Diffie-Hellman key exchange.

5.3.1 Direct Products of Groups

The direct product of two groups $(G_1,{\ast }_1,e_1)$ and $(G_2,{\ast }_2,e_2)$ is a new group formed by combining the elements of $G_1$ and $G_2$ as ordered pairs. The direct product is denoted as $(G_1\times G_2,\ast ,(e_1,e_2))$, where the set is $G_1\times G_2=\{(a,b)|a\in G_1,b\in G_2\}$, and the operation $\ast$ is performed component-wise:

$(a,b)\ast (c,d)=(a{\ast }_{1}c,b{\ast }_{2}d)$

Key Properties:

• The neutral element of the direct product is $(e_1,e_2)$, where $e_1$ and $e_2$ are the identity elements of $G_1$ and $G_2$ respectively.
• The inverse of an element $(a,b)$ is $(a^{-1},b^{-1})$, where $a^{-1}$ and $b^{-1}$ are the inverses of a and b in $G_1$ and $G_2$ respectively.

Example: Let $G_1=({\mathbb{Z}}_2,+)$ and $G_2=({\mathbb{Z}}_3,+)$ be the group of integers modulo 2 and 3, respectively. The direct product $G_1\times G_2$ consists of the elements:

$\{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)\}$

The operation is addition modulo 2 for the first element and modulo 3 for the second element, so that $(1,1)+(1,2)=(0,0)$.

5.3.2 Group Homomorphisms

A group homomorphism is a function $\varphi$ that maps elements from one group to another while preserving the group structure. Given two groups $(G_1,{\ast }_1,e_1)$ and $(G_2,{\ast }_2,e_2)$, a function $\varphi :G_1\to G_2$ is a homomorphism if for all $a,b\in G_1$:

$\varphi (a{\ast }_{1}b)=\varphi (a){\ast }_2\varphi (b)$

Key Properties:

• Homomorphisms map the identity element of one group to the identity element of the other group.
• Homomorphisms preserve inverses.

If the mapping $\varphi$ is also a bijection, then $G_1$ and $G_2$ are said to be isomorphic, and this mapping is called an isomorphism.

5.3.3 Subgroups

A subgroup is a subset $H$ of a group $G$ that is itself a group under the same binary operation as $G$. To be a subgroup, $H$ must satisfy the following conditions:

1. Closure: For all $a,b\in H$, $a\ast b\in H$.
2. Identity: The identity element $e$ of $G$ must also be in $H$.
3. Inverses: For all $a\in H$, the inverse $a^{-1}$ must also be in $H$.

Examples:

• For any group $G$, the set containing only the neutral element is a subgroup of G, often called the trivial subgroup.
• For any group $G$, the group $G$ itself is a subgroup of $G$.
• The set of even integers is a subgroup of the integers under addition.

5.3.4 The Order of Group Elements and of a Group

Order of a Group Element: The order of an element $a$ in a group $G$, denoted $ord(a)$, is the smallest positive integer $n$ for which $a^n=e$, where e is the identity element. If no such $n$ exists, the order of $a$ is infinite. * This definition relies on using an element $a$ as the base and iteratively performing the group’s operation (e.g. $+,\cdot$) on itself over and over until the neutral element is achieved.

Order of a Group: The order of a group G, denoted $|G|$, is the number of elements in the group. A group with a finite number of elements is called a finite group; otherwise, it is an infinite group.

5.3.5 Cyclic Groups

A cyclic group is a group that can be generated by a single element. This means that every element in the group can be obtained by repeatedly applying the group operation to a single element (the generator) and its inverse. If $g$ is a generator of group $G$, it is typically written: $G=⟨g⟩$.

5.3.6 Application: Diffie-Hellman for General Groups

The Diffie-Hellman key agreement protocol, a fundamental cryptographic technique, can be generalized to work with any cyclic group, not just the group of integers modulo a prime. The security of the protocol relies on the computational difficulty of solving the discrete logarithm problem within that specific group.

5.3.7 The Order of Subgroups: Lagrange’s Theorem

Lagrange’s Theorem is a fundamental result in group theory that restricts the size of subgroups within finite groups:

• Lagrange’s Theorem: If $G$ is a finite group and $H$ is a subgroup of $G$, then the order of $H$, $|H|$, divides $|G|$.

Corollaries of Lagrange’s Theorem:

1. The order of every element of a finite group divides the order of the group.
2. For a finite group $G$, it holds that $a^{|G|}=e$ for every $a\in G$ where e is the neutral element.

5.3.8 The Group ${\mathbb{Z}}_m^{\ast }$ and Euler’s Function

The set ${\mathbb{Z}}_m^{\ast }$ is of central importance in many applications related to group theory. It consists of all elements in the set ${\mathbb{Z}}_m$ that possess a multiplicative inverse.

• The multiplicative inverse of an element $a$ holds only if there exist integers $n,m$ such that $an+bm=1$, i.e. $a$ and $m$ are relatively prime.

Euler’s Totient Function: denoted by $\varphi (m)$, is the number of integers that are smaller than $m$ while still being relatively prime. It is formally defined as:

$\varphi (m)=|Z_m^{\ast }|$

The value of Euler’s Totient is the number of integers from the set that possess a multiplicative inverse.

5.4 Application: RSA Public-Key Encryption

TLDR: This section describes the RSA public-key cryptosystem, a cornerstone of modern secure communication. It explains how RSA relies on the difficulty of factoring large numbers and covers key generation, encryption, and decryption processes. It concludes with how the cryptosystem can be used for key management, digital signitures and some hints on its security.

5.4.1 e-th Roots in a Group

Before diving into RSA, it’s important to understand the concept of an e-th root in a group. In a group $G$ (under multiplication), the e-th root of an element $a\in G$ is another element $b\in G$ such that:

$b^e=a$

Not all elements have e-th roots, and if they do, the root doesn’t have to be unique. Also, most importantly, there may not be an efficient algorithm for calculating the $e$-th root of an element. RSA exploits this potential difficulty.

5.4.2 Description of RSA

RSA (Rivest-Shamir-Adleman) is a public-key cryptosystem that revolutionized secure communication. Its security rests on the mathematical properties of modular arithmetic and the presumed intractability of factoring large numbers.

Here’s a breakdown of the key steps in RSA:

1. Key Generation:

   • Alice chooses two distinct, large prime numbers, $p$ and $q$. The larger the primes, the better the security (typically 1024 to 4096 bits each).
   • Alice calculates $n=p\cdot q$. This product, $n$, is called the modulus.
   • Alice computes Euler’s totient function, $\varphi (n)=(p-1)\cdot (q-1)$. This function calculates the number of integers between $1$ and $n$ that are coprime to $n$.
   • Alice selects an integer $e$ such that $1<e<\varphi (n)$ and $\text{gcd}(e,\varphi (n))=1$. $e$ is the public exponent.
   • Alice computes the modular multiplicative inverse of $e$ modulo $\varphi (n)$, denoted $d$. This means finding an integer $d$ such that $e\cdot d\equiv 1(\mathrm{mod}\varphi (n))$. $d$ is the private exponent.

   Alice’s public key is the pair $(n,e)$, which can be freely distributed to anyone. Alice’s private key is the pair $(n,d)$, which she keeps secret.

2. Encryption: Bob wants to send a message $m$ to Alice. Bob must ensure that $m$ is an integer such that $1\le m<n$. He uses Alice’s public key $(n,e)$ to encrypt the message: $c=m^e(\mathrm{mod}n)$ where $c$ is the ciphertext.

3. Decryption: Alice receives the ciphertext $c$ from Bob. She uses her private key $(n,d)$ to decrypt the message: $m=c^d(\mathrm{mod}n)$ Because $e\cdot d\equiv 1(\mathrm{mod}\varphi (n))$, it can be shown that this decryption correctly recovers the original message $m$.

5.4.3 On the Security of RSA *

The security of the RSA cryptosystem is primarily based on the assumed difficulty of the factoring problem.

Factoring Problem: Given a large composite number $n$, find its prime factors $p$ and $q$. It can be proved that RSA is secure only if there exists no good primality testing algorithms.

If an attacker can factor $n$ into $p$ and $q$, they can compute $\varphi (n)=(p-1)(q-1)$, which is a necessary condition for the system to be working as is, and then easily compute the private key $d$, thus breaking the system. While no polynomial-time algorithm is known for factoring large numbers on classical computers, recent theoretical advances in quantum computing show promise for being able to efficiently find an exponential-time algorithm to break RSA (Shor’s Algorithm). Therefore new key management cryptosystems that are more resistant against attacks on a quantum-computing system must be implemented.

5.4.4 Digital Signatures *

RSA can be adapted to create digital signatures, providing authentication and non-repudiation.

5.5 Rings and Fields

TLDR: This section introduces rings and fields, two crucial algebraic structures with two operations: addition and multiplication. Key concepts include the definition of a ring, units, divisors, zero divisors, integral domains, polynomial rings, and fields.

5.5.1 Definition of a Ring

A ring is an algebraic structure consisting of a set $R$ equipped with two binary operations, addition (+) and multiplication ($\cdot$), satisfying the following axioms:

• Addition: $(R,+,-,0)$ is a commutative (abelian) group. This implies:

  • Closure under addition: For all $a,b\in R$, $a+b\in R$.
  • Associativity of addition: For all $a,b,c\in R$, $(a+b)+c=a+(b+c)$.
  • Existence of a neutral element (additive identity), 0: There exists an element $0\in R$ such that for all $a\in R$, $a+0=0+a=a$.
  • Existence of additive inverses: For each $a\in R$, there exists an element $-a\in R$ such that $a+(-a)=(-a)+a=0$.
  • Commutativity of addition: For all $a,b\in R$, $a+b=b+a$.

• Multiplication: $(R,\cdot ,1)$ is a monoid. This implies:

  • Closure under multiplication: For all $a,b\in R$, $a\cdot b\in R$.
  • Associativity of multiplication: For all $a,b,c\in R$, $(a\cdot b)\cdot c=a\cdot (b\cdot c)$.
  • Existence of a multiplicative identity, 1: There exists an element $1\in R$ such that for all $a\in R$, $a\cdot 1=1\cdot a=a$.

• Distributive Law: Multiplication distributes over addition:

  • For all $a,b,c\in R$, $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ (left distributivity).
  • For all $a,b,c\in R$, $(a+b)\cdot c=(a\cdot c)+(b\cdot c)$ (right distributivity).

A ring is called commutative if multiplication is commutative, i.e., if for all $a,b\in R$, $a\cdot b=b\cdot a$.

5.5.2 Units and the Multiplicative Group of a Ring

A unit in a ring $R$ is an element $u\in R$ that possesses a multiplicative inverse. In other words, there exists an element $v\in R$ such that $u\cdot v=v\cdot u=1$, where 1 is the multiplicative identity. This element $v$ is also called the multiplicative inverse of $u$ and is denoted by $u^{-1}$.

The set of all units in a ring $R$ is denoted by $R^{\ast }$. The units of a ring themselves form a group under multiplication, called the multiplicative group of units or group of units, written as $(R^{\ast },\cdot )$.

Example: In the ring of integers $\mathbb{Z}$, the units are 1 and -1, since $1\cdot 1=1$ and $(-1)\cdot (-1)=1$. Therefore, ${\mathbb{Z}}^{\ast }=\{-1,1\}$.

5.5.3 Divisors

The concept of divisibility extends to rings. For elements $a$ and $b$ in a ring $R$, we say that $a$ divides $b$, denoted $a\mid b$, if there exists an element $c\in R$ such that $b=a\cdot c$. In this case, $a$ is called a divisor of $b$, and $b$ is called a multiple of $a$.

5.5.4 Zerodivisors and Integral Domains

Zerodivisor

An element $a$ in a commutative ring $R$ is called a zerodivisor if $a\ne 0$ and there exists a non-zero element $b\in R$ such that $a\cdot b=0$.

Integral Domain

An integral domain is a non-trivial (i.e., it contains more than one element, so that $0\ne 1$) commutative ring with no zerodivisors. This means that if $a\cdot b=0$ for elements $a$ and $b$ in an integral domain, then either $a=0$ or $b=0$.

5.5.5 Polynomial Rings

A polynomial ring, denoted $R[x]$, is the set of all polynomials in the variable $x$ with coefficients from a ring $R$. A general polynomial in $R[x]$ looks like:

$p(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+...+a_{1}x+a_0$, where $a_i\in R$.

• Addition: Polynomial addition is defined as term by term, or by adding the coefficients corresponding to the same power of x.
• Multiplication: Polynomial multiplication is defined using the distributive property of real numbers. For any $a,b\in R$ and any natural numbers i, j:
  • $x^i\cdot x^j=x^{i+j}$
  • $a{x}^i\cdot b{x}^j=(a\cdot b)x^{i+j}$

5.5.6 Fields

A field is a special type of ring $F$ in which every non-zero element is a unit. This means that $F$ is a group under multiplication, excluding the zero element. In other words, a field is a commutative ring where every non-zero element has a multiplicative inverse. If every element is a unit, the algebra is called field.

In summary, the defining properties of a field $F$ are:

• It’s a commutative ring with $1\ne 0$.
• Every nonzero element $a\in F$ is an invertible element which implies there exists $a^{-1}$ s.th. $a\cdot a^{-1}=1$.

Examples:

• The set of rational numbers $\mathbb{Q}$ is a field under addition and multiplication.
• The set of real numbers $\mathbb{R}$ is a field.
• The set of complex numbers $\mathbb{C}$ is a field.
• $\mathbb{Z}$ (the integers) is NOT a field because, for example, the integer 2 does not have an inverse.
• ${\mathbb{Z}}_p$ is a field, where $p$ is any prime number.

5.6 Polynomials over a Field

TLDR: This section discusses the properties of polynomials with coefficients from a field, focusing on factorization, irreducibility, division, and analogies to the integers. Key concepts include irreducible polynomials, the division property, and the link to Euclidean domains.

5.6.1 Factorization and Irreducible Polynomials

Factorization

Similar to how integers can be broken down into prime factors, a polynomial $f(x)$ in $F[x]$ can be factored into a product of polynomials, i.e. you find two polynomials, $g(x)$ and $h(x)$, with coefficients in $F$ such that $f(x)=g(x)\cdot h(x)$.

Example: If $F=\mathbb{R}$ and $f(x)=x^2-1$, then you find $g(x)=x+1$ and $h(x)=x-1$, s.th. $f(x)=g(x)\cdot h(x)=(x+1)(x-1)$.

Irreducible Polynomials

An irreducible polynomial $f(x)$ in $F[x]$ is a non-constant polynomial that cannot be factored into a product of two non-constant polynomials of lower degree. The analogy to this concept with integers is that it is a prime-number in the polynomial domain. That is to say, it cannot be factored by anything except for 1 and itself.

Important Note: The irreducibility of a polynomial depends on the field $F$. A polynomial may be irreducible over one field but reducible over another.

Example: The polynomial $x^2+1$ is irreducible over $\mathbb{R}[x]$, because it has no real roots. However, it can be factored in $\mathbb{C}[x]$ as $(x+i)(x-i)$, where $i=\sqrt{-1}$.

5.6.2 The Division Property in $F[x]$

This key property is similar to integer division with remainders. For any two polynomials $f(x)$ and $g(x)$ in $F[x]$ with $g(x)\ne 0$, there exist unique polynomials $q(x)$ (the quotient) and $r(x)$ (the remainder) such that:

$f(x)=q(x)\cdot g(x)+r(x)$,

where the degree of the remainder $r(x)$ is strictly less than the degree of the divisor $g(x)$, i.e., $deg(r(x))<deg(g(x))$.

Example: Let $F=\mathbb{Q}$ and $f(x)=x^3+2x^2+x-1$, $g(x)=x^2+1$. Then, we can write $f(x)=(x+2)\cdot g(x)+(0x-3)$, or

$x^3+2x^2+x-1=(x+2)(x^2+1)+(-3)$.

This means that $q(x)=x+2$ and $r(x)=-3$. Note that, as required, $\text{deg}(r(x))=0<deg(g(x))=2$.

This property is fundamental to many algebraic manipulations, including finding greatest common divisors and constructing finite fields.

5.6.3 Analogies Between $\mathbb{Z}$ and $F[x]$, Euclidean Domains *

There are profound parallels between the integers $\mathbb{Z}$ and the polynomial ring $F[x]$ over a field $F$. Both exhibit similar structural properties, making them examples of Euclidean domains. A Euclidean domain is an integral domain that satisfies certain properties with a degree/size function.

Key Analogies:

1. Division Algorithm: Both have a well-defined division algorithm (division with a remainder), where remainders are “smaller” than the divisor.
2. Greatest Common Divisor (GCD): In both $\mathbb{Z}$ and $F[x]$, one can define the GCD of two elements. Euclidean algorithm is the most common procedure for defining a greates common divisor:
   • The Euclidean algorithm is based on the division algorithm to compute GCDs efficiently.
3. Unique Factorization: It provides a way to express numbers and polynomials through prime numbers or irreducible polynomials. The procedure is based on applying the Euclidean algorithm.

Consequence: Understanding these similarities allows one to transfer techniques and results from number theory to polynomial rings and vice versa. Concepts like GCDs, prime factorization, and congruences can be generalized to the realm of polynomials.

5.7 Polynomials as Functions

TLDR: This section explores the connection between polynomials and functions, focusing on polynomial evaluation, roots, and polynomial interpolation. The key insight is that polynomials over a field can be treated as functions, and this perspective has important implications for various applications.

5.7.1 Polynomial Evaluation

A polynomial $f(x)$ over a field $F$ can be interpreted as a function from $F$ to $F$. This is done by defining evaluation of $f(x)$ at a value $a\in F$ as simply substituting $a$ for the variable $x$ in the polynomial expression and performing the resulting arithmetic operations within the field $F$. The result is denoted $f(a)$.

Example: Let $F=\mathbb{Q}$ (the rational numbers) and $f(x)=x^2+2x-1$. Then,

• $f(0)=0^2+2(0)-1=-1$
• $f(1)=1^2+2(1)-1=2$
• $f(-1)=(-1{)}^2+2(-1)-1=-2$

Polynomial evaluation establishes a mapping $F\to F:a\mapsto f(a)$ that converts a polynomial to a function.

5.7.2 Roots

A root (also called a zero) of a polynomial $f(x)$ in a field $F$ is a value $a\in F$ such that $f(a)=0$. In other words, when you evaluate the polynomial at the root, the result is the additive identity (zero) in the field. The roots of a polynomial are often useful and crucial for solving polynomial equations.

Example: Let $F=\mathbb{R}$ (the real numbers) and $f(x)=x^2-4$. Then,

• $f(2)=2^2-4=0$, so $x=2$ is a root of $f(x)$.
• $f(-2)=(-2{)}^2-4=0$, so $x=-2$ is a root of $f(x)$.

A fundamental theorem from basic algebra then states that a polynomial of degree $n$ can have at most $n$ different roots.

5.7.3 Polynomial Interpolation

Polynomial Interpolation refers to the process of constructing a polynomial that passes through a given set of data points. Given $n$ distinct points $(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$ where $a_i$ and $b_i$ are values in a field $F$ with $a_i\ne a_j$ for all $i\ne j$, there exists a unique polynomial $f(x)$ of degree at most $n-1$ such that $f(a_i)=b_i$ for all $i=1,2,...,n$. This unique polynomial interpolates the points.

Polynomial interpolation has many applications, such as approximation theory, data fitting, cryptography, and coding theory. The method allows us to approximate functions using a polynomial when dealing with large datasets in a computational environment.

Example: Find the linear polynomial (degree 1) that goes through (0, 1) and (1, 2). In this case, the linear polynomial is $x+1$.

Lagrange Interpolation Theorem: Let the interpolation formula $f(x)$ be defined to be $f(x)={\Sigma }_{i=0}^n{y}_i{L}_i(x)$ where $L_i(x)={\Pi }_{j=0,j\ne i}^n\frac{x-x_j}{x_i-x_j}$. Then if you substitute the interpolation point $x_i$ in for $x$ in $L_i$, we have $L_i(x_i)=1$ and if you substitute any other interpolation point $x_j$ in for $x$ in $L_i$, we have $L_i(x_j)=0$. Hence we can show that it meets all the conditions and so that is all that is required.

5.8 Finite Fields

TLDR: This section focuses on finite fields, particularly their construction using polynomial arithmetic. Key concepts include the ring $F[x]/m(x)$, how to create extension fields from finite fields, and some fundamental properties about finite field orders and existence.

5.8.1 The Ring $F[x]/m(x)$

Let $F$ be a field, and let $m(x)$ be a polynomial in $F[x]$. The ring $F[x]/m(x)$ (read as “F[x] modulo m(x)”) is constructed by considering polynomials over $F$, but identifying any two polynomials that have the same remainder when divided by $m(x)$.

Key Ideas:

• Congruence Modulo a Polynomial: Two polynomials, $a(x)$ and $b(x)$, are said to be congruent modulo $m(x)$, denoted $a(x)\equiv b(x)(\mathrm{mod}m(x))$, if $m(x)$ divides their difference: i.e., $m(x)|(a(x)-b(x))$.
• Remainders: The elements of $F[x]/m(x)$ are the possible remainders upon division by $m(x)$. This means the elements have a degree that is less than the degree of $m(x)$. If $m(x)$ has degree $d$, then the ring is the set of all polynomials in $F[x]$ having degree at most $d-1$.
• Operations: Addition and multiplication in $F[x]/m(x)$ are performed as follows:
  1. Perform the usual polynomial addition or multiplication in $F[x]$.
  2. Divide the result by $m(x)$ to obtain a remainder $r(x)$.
  3. The remainder $r(x)$ is the result of the operation in $F[x]/m(x)$.

5.8.2 Constructing Extension Fields

We can construct extension fields from finite fields using irreducible polynomials. If $F$ is a finite field and $m(x)$ is an irreducible polynomial of degree $d$ over $F$, then $F[x]/m(x)$ is a field with $|F{|}^d$ elements. This process effectively extends the base field $F$ to a larger field containing the roots of $m(x)$.

Why Irreducible Polynomials?

The irreducibility of $m(x)$ is crucial. If $m(x)$ were reducible (i.e., could be factored into non-constant polynomials), then $F[x]/m(x)$ would contain zero-divisors and therefore would not be a field (it would only be a ring).

Therefore, an irreducible polynomial is required to create the structure of a field. The condition of having no zerodivisors is an integral domain. Irreducible is used when there are no “smaller” non-invertible elements in the polynomial that divide the larger polynomial.

5.8.3 Some Facts About Finite Fields *

This subsection presents, without proof, two fundamental facts about finite fields:

• Order is a Prime Power: Every finite field has order (number of elements) $q$, where $q=p^n$ for some prime number $p$ and some positive integer $n$. The prime $p$ is called the characteristic of the field.
• Uniqueness: For every prime power $p^n$, there exists a unique (up to isomorphism) finite field of order $p^n$. This field is commonly denoted as $GF(p^n)$ or ${\mathbb{F}}_{p^n}$. These facts justify the use of $GF(p^n)$ and the term extension field.

5.9 Application: Error-Correcting Codes

TLDR: This section introduces the application of algebra to error-correcting codes, a vital tool in reliable communication and data storage. It focuses on the construction of codes using polynomial evaluation and interpolation, stating formally their properties.

5.9.1 Definition of Error-Correcting Codes

An error-correcting code is a method of encoding data that allows for the detection and correction of errors that may occur during transmission over a noisy channel or when reading data from a storage medium. This is achieved by adding redundancy to the original information.

More formally, an $(n,k)$-encoding function $E$ for some alphabet $A$ is an injective function:

$E:A^k\to A^n$

where:

• $A$ is the alphabet (e.g., $\{0,1\}$ for binary codes, or $GF(q)$ for a code over a finite field).
• $k$ is the number of information symbols (the length of the message to be encoded).
• $n$ is the number of encoded symbols (the length of the codeword). Since $n>k$, this is what introduces redundancy.
• $A^k$ is the set of all possible messages of length $k$ using symbols from $A$.
• $A^n$ is the set of all possible codewords of length $n$ using symbols from $A$.
• The elements $c\in A^n$ are the codewords.
• The set $C=\{c\in A^n|\exists m\in A^k,E(m)=c\}$ is called the code.
• The number of code words is $k$ and is called dimension.
• The number of code word symbols is $n$ and is called length.

The function $E$ maps a message of length $k$ to a codeword of length $n$.

5.9.2 Decoding

The process of decoding involves receiving a possibly corrupted message and determining the original message that was most likely sent. This is achieved through a decoding function:

$D:A^n\to A^k$

That maps the received codeword, that may contain errors, to the intended source message of length $k$. The design of decoding functions is crucial for the effectiveness of an error-correcting code.

Hamming Distance

To describe the error-correcting properties of a code more formally, we need the concept of Hamming distance. The Hamming distance between two strings of equal length over a finite alphabet $A$ is the number of positions at which the two strings differ.

Minimum Distance

The minimum distance $d_{min}(C)$ of an error-correcting code $C$ is the minimum Hamming distance between any two distinct codewords in $C$:

$d_{min}(C)=\min \{d_H(c_i,c_j)\mid c_i,c_j\in C,c_i\ne c_j\}$

where $d_H$ is the Hamming distance. A code that has a small value of $d_{min}$ is not very useful in error correction since only a few changes would lead to another valid codeword.

Relationship between Minimum Distance and Error Correction

A code with a minimum distance $d_{min}$ can correct up to $t$ errors, where $t$ is given by

$t=\lfloor \frac{d_{min}-1}{2}\rfloor$

Where the Hamming distance is $d_H$. The error-correcting and error-detecting capabilities of a code depend directly on its minimum distance. A code with minimum distance $d_{min}$ can detect up to $d_{min}-1$ errors. If the number of errors is less than or equal to t, the correct codeword can be unambiguously identified and the source message can be recovered. For example, for the case where the number of errors are more than t, there are multiple possible original code words which makes it impossible to correctly detect the source message.

5.9.3 Codes Based on Polynomial Evaluation

A powerful method for constructing error-correcting codes utilizes polynomial evaluation and interpolation. This method leverages the properties of finite fields, often denoted by $GF(q)$, where q is a prime power. Assume a field $A=GF(q)$ for some $q$:

Let $m=(a_0,...,a_{k-1})\in GF(q{)}^k$ be the source message. Define $p(x)=a_{k-1}{x}^{k-1}+...+a_{1}x+a_0$ where $a_i\in GF(q)$ for all $i$, meaning, that the coefficients are from the finite field. Let $n$ elements $x_0,...,x_{n-1}\in GF(q)$ such that $n>=k$. Let the encoding operation be $E(m)=(p(x_0),...,p(x_{n-1}))$. This means we have mapped the source message $m$ to $GF(q{)}^n$ where the length of $m$ is k and the length of the corresponding encoded message is $n$.

This code has minimum distance $n-k+1$. The proof of this is that if two source messages $m$ and $m^{\prime }$ where different, then they have different polynomials corresponding to the mapping $a(x)$ and $a^{\prime }(x)$. Since they differ, that means that the polynomials can intersect a maximum of $k-1$ times which means that there is a difference of values for $n-(k-1)=n-k+1$ between the original messages. This is very useful for error correction since the error correcting capability is $t=\lfloor \frac{n-k}{2}\rfloor$.

For large values of $n$, only very few errors can be made such that polynomial interpolation to recover the source message is always correctly computed. To increase the error-correcting power, a larger code is needed which means that a larger prime base has to be chosen such that the above expression yields the same size field. A larger message can also be chosen to increase code power but the trade off is that only very few errors can occur to safely perform polynomial interpolation.

Next Chapter: Chapter 6 - Logic