deletions | additions       diff --git a/chapter_0_Mathematical_Review_Elementary__2.tex b/chapter_0_Mathematical_Review_Elementary__2.tex  new file mode 100644  index 0000000..bf5cae5  --- /dev/null  +++ b/chapter_0_Mathematical_Review_Elementary__2.tex 
...
\chapter*{0. Mathematical Review: Elementary Set Theory}  \section{Sets and Operators}  The \textbf{Set} is a Mathematical Entity undefinable precisely: we could say that is a collection of elements of various species.   We could imagine $A$ as the set of English Alphabet letters,or the set of the people living on the Earth, or a collection of songs, etc... . We could represent sets in different ways:  \begin{itemize}  \item Describing the property of the elements in braces:  \begin{center}  $A=\left\lbrace \right. $The set of the letters of the English alphabet$\left\rbrace \right. $  \end{center}  \item Saying the elements one-to-one:  \begin{center}  $A=\left\lbrace a,b,c,d, \ldots \right\rbrace $  \end{center}  \item The graphic representation by using the Euler-Venn Diagram:  \begin{figure}[h]  \centering  \includegraphics[scale=0.2]{EV.png}  \end{figure}  \end{itemize}  \ \linebreak  Now if e.g. a letter \textit{a} belongs to the set $A$ we will write $$a\in A \, $$ while if a number e.g. $1$ does not belong to $A$ we will write $$ 1\not\in A.$$ The set that does not contain elements is called \textbf{Empty Set} and is represented by the symbol $\varnothing. $\\  If we consider two sets $A$ and $B$ and one of them, $B$, is included in the other, $A$, we say that $B$ is \textit{subset} of $A$ and we represents it by writing $$B \subseteq A.$$  We define \textbf{Power Set} of $A$, $\mathcal{P}(A)$, the set of all subsets of $A$, including $A$ and $\varnothing$.  E.g.:  \begin{center}  $A=\lbrace a,b \rbrace$ \ \\ \ \\  $\mathcal{P}(A)=\big\lbrace \varnothing,A,\lbrace a \rbrace, \lbrace b \rbrace \big\rbrace$  \end{center}   We note that if $A$ has $n$ elements, $\mathcal{P}(A)$ has $2^{n}$ elements.\\  It's possible to define some operators over the sets that are: Union, Intersection,Complement and Cartesian Product.  \begin{itemize}  \item The \textbf{Union} represented by the symbol $\cup$ is the operator that given two sets $A$ and $B$ returns the set $A \cup B$ that contains the elements of both $A$ and $B$. \\  E.g.:  \begin{center}  $ A=\lbrace a,b\rbrace$ \ \\  $ B=\lbrace c,d \rbrace $ \ \\  $A \cup B =\lbrace a,b,c,d \rbrace$  \end{center}  \item The \textbf{Intersection} represented by the symbol $\cap$ is the operator that given two sets $A$ and $B$ returns the set $A \cap B$ that contains the elements that are in common between $A$ and $B$.\\  E.g.:  \begin{center}  $ \ \ \ \ \ A=\lbrace a,b\rbrace$ \ \\  $\ \ \ \ \ \ \ \ \ \ \ B=\lbrace a,b,c,d \rbrace $ \ \\  $A \cap B =\lbrace a,b \rbrace$  \end{center}  \item The \textbf{Complement} represented by the symbol $\setminus$ is the operator that given two sets $A$ and $B$ returns the set $A \setminus B$ that contains the elements of $A$ that don't belong to $B$.\\  E.g.:  \begin{center}  $\ \ \ \ \ \ \ \ \ \ \ A=\lbrace a,b,c,d \rbrace $ \ \\  $ \ \ \ \ \ B=\lbrace a,b\rbrace$ \ \\  $A \setminus B =\lbrace c,d \rbrace$  \end{center}  \item The \textbf{Cartesian Product} represented by the symbol $\times$ is the operator that given two sets $A$ and $B$ returns the set $A \times B$ that is the set of the ordered pairs obtainable taking the first element by $A$ and the second one by $B$.\\  \begin{center}  $ A=\lbrace a,b\rbrace$ \ \\  $ B=\lbrace c,d \rbrace $ \ \\  $A \times B =\lbrace (a,c),(a,d),(b,c),(b,d) \rbrace$  \end{center}  \end{itemize}  Starting by the Cartesian Product we will define the Relations. \ \\  \section{Relations}  Let $A$ and $B$ be two sets and $A \times B $ their Cartesian Product, we define \textbf{Relation} a subset $\mathcal{R}$ of $A \times B $. \ \\  E.g.:  \begin{center}  $A=\lbrace0,1,2\rbrace$ \ \\  $B=\lbrace-1,1\rbrace$ \ \\  $A \times B = \lbrace(0,-1),(0,1),(1,-1),(1,1),(2,-1),(2,1) \rbrace$ \ \\  we take e.g.: $\mathcal{R}= \lbrace(0,1),(2,-1) \rbrace$   \end{center}  and if we look we could say that this is the set of the pairs whose sum is 1 and so:  \begin{center}  $\mathcal{R}= \lbrace (a,b) \in A\times B \mid a+b=1 \rbrace$  \end{center}  or we could say that $a\mathcal{R} b \Leftrightarrow a+b=1$.\\   If we take $B=A$ then $A\times A=A^{2}$ and the relation $ \mathcal{R}$ is a binary relation.  Some properties of binary relations:  \begin{itemize}  \item \textbf{Reflexive} $$\forall a \in A \ \ \ \ a \mathcal{R} a $$  \item \textbf{Symmetric} $$\forall a,b \in A \ \ if \ a \mathcal{R} b \Rightarrow b \mathcal{R} a $$  \item \textbf{Antisymmetric} $$\forall a,b \in A \ \ if \ a \mathcal{R} b \ and \ b \mathcal{R} a \Rightarrow a=b$$  \item \textbf{Transitive} $$\forall a,b,c \in A \ \ if \ a \ \mathcal{R} b \ and \ b \mathcal{R} c \Rightarrow a \mathcal{R} c$$  \end{itemize}  and so we could define   \begin{center}  \textbf{Equivalence Relation} if it is Reflexive,Symmetric and Transitive \ \\  \textbf{Order Relation} if it is Reflexive, Antisymmetric and Transitive.  \end{center}  \ \\  In particular, let $\mathcal{R}$ be an Equivalence Relation over the set $A$, we could regroup the elements that are related each other in the same class with an unique representative, i.e. $x$, and this is called \textit{equivalence class of the element $x$}, denoted by $[x]$. Finally we call \textbf{Quotient Set} :  \begin{center}  $A_{/\mathcal{R}}=\big\lbrace[x] \ \ | \ \ x \in A \big\rbrace$  \end{center}  The quotient set will play a main role in the construction of the cryptography over particular finite sets.  \section{Functions}  In the set of the relations between the $A$ and $B$, we distinguish special relations that we call \textbf{Functions}.  A function associates to every element of the set $A$ only one element of the set $B$. We say that if $f$ is a function between $A$ and $B$, we write:  \begin{center}  $f:A \rightarrow B$  \end{center}  and if $b \in B$ is the (only one) element related to $a \in A$ we write  \begin{center}  $a \mapsto f(a)=b$  \end{center}  and $b$ is called \textbf{image} of $a$ and the set of the images is $$Imf=\lbrace b \in B \ | \ \exists a \in A \ s. \ t. \ f(a)=b \rbrace.$$  The set $A$ is called \textbf{Domain} while the set $B$ is the \textbf{Codomain}.\\  Functions could have different properties:  \begin{itemize}  \item \textbf{Injective Function}\ \\  A function $f$ from $A$ to $B$ is called \textbf{Injective} if to diferent elements of $A$, $f$ associates different elements of $B$:  $$x_{1},x_{2} \in A, \ x_{1}\neq x_{2} \Rightarrow f(x_{1}) \neq f(x_{2}) $$ or in another form:   $$if \ f(x_{1}) = f(x_{2}) \Rightarrow x_{1}=x_{2}$$  \item \textbf{Surjective Function} \\  A function $f$ from $A$ to $B$ is called \textbf{Surjective} if every element of $B$ is image of an element belonging to $A$:  $$\forall b \in B \ \exists a \in A \ \ s. \ t. \ f(a)=b $$ and this fact implies that $Imf = B$  \item \textbf{Bijective Function} \\  A function $f$ from $A$ to $B$ is called \textbf{Bijective} if it is both injective and surjective. And so$$\forall b \in B \ \exists ! a \in A \ \ s. \ t. \ f(a)=b $$\\  \end{itemize}  \ \\  Let $f: A\rightarrow B $ is a bijective function, then f is \textbf{Invertible}, so it exists the inverse function of $f$ that we denote by $f^{-1}$:  $$f^{-1}: B \rightarrow A $$  $$b\mapsto f^{-1}(b)=a $$  where $a$ is the only element such that $f(a)=b$.  \section{Sets with Operations: Groups, Rings and Fields}  \subsection{Groups}  Let $G$ be a set. We define over $G$ one binary internal operation that we call $\star$,"Addition": binary because it acts from $G \times G$, and internal because it goes to $G$ .  $$\star : G \times G \rightarrow G $$  $$ \ \ \ \ \ \ \ \ \ (a,b) \mapsto a \star b$$  We say that $(G,\star)$ is a \textbf{Group} the operation $\star$ satisfies the following properties:  \begin{itemize}  \item[$\bullet$] \textbf{Associative Property}   $$\forall a,b,c \in G \ \ \ a\star (b \star c)=(a \star b) \star c = a \star b \star c$$   \item[$\bullet$] \textbf{Existence of the Unit}   $$\exists e \in G \ s. \ t. \ \forall a \in G \ \ a \star e =e \star a= a$$  \item[$\bullet$] \textbf{Existence of the Inverse}  $$\forall a \in G \ \exists b \in G \ \ s. \ t. \ a \star b=b\star a = e $$  \ \\  \end{itemize}  If the operation satisfies also:  \begin{itemize}  \item[$\bullet$] \textbf{Commutative Property}  $$\forall a,b \in G \ \ \ \ a\star b= b\star a$$  $G$ is called \textbf{Abelian Group}  \end{itemize}  \subsection{Rings}  Let$ A$ be a set. We would define two binary operations over A that are $\star$ and $\cdot$."Addition" and "Multiplication".\\  $(A,\star,\cdot)$ is called \textbf{Ring} if:  \begin{itemize}  \item $A$ is an Abelian Group under $\star$;  \item $A$ is a \textit{Monoid} under $\cdot$ : it satisfies Associative Property and Existence of the Unit;  \item The $\cdot$ is distributive with respect to the $\star$, left and right :  $$\forall a,b,c \in A \ \ \ \ a \cdot (b \star c )= a \cdot b \star a \cdot c $$  $$\forall a,b,c \in A \ \ \ \ (b \star c ) \cdot a = b \cdot a \star c \cdot a $$   \end{itemize}  We will call the unit of $\star$ as $0_{A}$, and the unit of $\cdot$ as $1_{A}$  \ \\  It could happen that two non-zero elements, when "multiplied", give as result $0_{A}$, in other words:  $$\exists a,b \in A \ \ \ \ \ a,b \neq 0_{A} \ \ \ s. \ t. \ a \cdot b= 0_{A} $$  These elements are called \textbf{Zero Divisors}.  \subsection{Fields }  Let $F$ be a set. We define over $F$ the two previous operations $\star$ and $\cdot$; we call $(F,\star,\cdot)$ a \textbf{Field} if:  \begin{itemize}  \item $F$ is an Integral Domain  \item Every non-zero element of $F$ has multiplication inverse   \end{itemize}  \section{Number Sets: the Properties of $\mathbb{Z}$}  \subsection{Number Sets}  The numbers that we know are divided in sets that are one included in the other:  \begin{itemize}  \item \textbf{Natural Numbers} $\mathbb{N}$ \\  The natural numbers are the ones given by the "nature", one apple, two trees, etc... they are all non negative.  $$\mathbb{N}=\lbrace1,2,3,4, \ldots \rbrace $$   \item \textbf{Integer Numbers} $\mathbb{Z}$ \\  The positive numbers united with 0 and the negative numbers (defined as the natural numbers with the minus beside).  $$\mathbb{Z}=\lbrace-2,-1,0,1,2, \ldots \rbrace $$  \item \textbf{Rational Numbers} $\mathbb{Q} $ \\  The Rational Numbers are the ones that are expressible by fraction.  $$\mathbb{Q}=\Bigg\lbrace -\dfrac{2}{3},0, 1, \dfrac{5}{3}, \ldots \Bigg\rbrace $$  \item \textbf{Real Numbers} $\mathbb{R} $ \\  All the numbers of our reality, rational and irrational.  $$\mathbb{R}=\Bigg\lbrace -\dfrac{2}{3},0, \sqrt{2}, \dfrac{5}{3}, \pi, \ldots \Bigg\rbrace $$  \item \textbf{Complex Numbers} $\mathbb{C}$ \\  The numbers that are constructed starting by assuming $\sqrt{-1}=i$ the \textbf{imaginary unit}. They have Real Part and Imaginary Part.  $$\mathbb{C}=\Bigg\lbrace -i,0,i,1+i,2+3i \ldots \Bigg\rbrace $$  \end{itemize}  As we immediately see the relation between these sets is:  $$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C} $$  The Cryptography and the Cryptocurrencies, in some way, use the properties of the integers to found their basis.  \subsection{The Set of Integers $\mathbb{Z}$}  We would recall some properties of the integers as the division, the existence of greatest common divisor and so on.  Firstly it's easy to prove that $(\mathbb{Z},+,\cdot)$ is a Ring, in particular is an Integral Domain. It's not a Field because e.g.  doesn't exist an integer $x \in \mathbb{Z}$ such that $2x=1$.  Let $a,b \in \mathbb{Z}, \ b\neq 0$, we say that $b$ divides $a$ and we write $b \mid a$, if $\exists c \in \mathbb{Z} \ \ s. \ t. \ \ a=b \cdot c $ .\\  The numbers $b$ and $c$ are \textbf{Divisors} for $a$ and it's clear that $\forall a,b,c \in \mathbb{Z} $ if $a \mid b$ and $a \mid c $ then $a \mid rb+sc \ \ \ \forall r,s \in \mathbb{Z} $. \\  Given two integers we could research the biggest number that divides both of them.   Let $a,b \in \mathbb{Z}, \ \ \ a,b\neq 0$, we define \textbf{Greatest Common Divisor} between $a$ and $b$, $gcd(a,b)$ a number $d$ such that:  \begin{itemize}  \item $d \mid a \ $ and $ \ d \mid b $  \item $\forall d' \in \mathbb{Z}, \ s. \ t. \ d' \mid a \ $ and $\ d' \mid b \Rightarrow d' \mid d $  \end{itemize}  To research the gcd of two numbers $a,b$ we could naively write all the divisor of them and take the common that is greatest.\\  E.g.:\\  $a=18, b=12 $\ \\  $D(a)=\lbrace 1,2,3,6,9,18 \rbrace $\ \\  $D(b)=\lbrace 1,2,3,4,6,12 \rbrace $\ \\  The greatest one is $6$ then $gcd(a,b)=6$  \ \\  \ \\  The method described above is a naive way to research the gcd; another way is computing it by using the Euclidean Algorithm, but first let's introduce the \textbf{Euclidean Division}: \ \\  Let $a,b $ be integers, then $\exists q,r \in \mathbb{Z}$ (unique!) \textit{quotient} and \textit{remainder} such that $$a=b\cdot q + r \ \ \ \ \ 0 \leq r < \vert b \vert$$.  The \textbf{Euclidean Algorithm} is set up with a successive chain of Euclidean Divisions, until we find that the remainder is $0$ and the last non-zero remainder is the gcd of the two numbers. In other words:\\  Let $a,b \in Z$, let's say $b=r_{0} $ then  \begin{flushleft}  \begin{equation}  \begin{split}  &a=bq_{1}+r_{1} \ \ \ \ 0 \leq r_{1} < \vert b \vert \\  &b=r_{1}q_{2}+r_{2} \ \ \ \ 0 \leq r_{2} < r_{1} \\  &r_{1}=r_{2}q_{3}+r_{3} \ \ \ \ 0 \leq r_{3} < r_{2} \\  &\vdots \\  &r_{n-2}=r_{n-1}q_{n}+r_{n} \ \ \ \ 0 \leq r_{n} < r_{n-1} \\  &r_{n-1}= r_{n}q_{n+1} + r_{n+1} \ \ \ \ with \ \ \ r_{n+1}=0 \\  &r_{n}=gcd(a,b)  \end{split}   \end{equation}  \end{flushleft}  In general this algorithm takes $\log_{2} b + 2$ steps to find the greatest common divisor between $a$ and $b$.  \ \\  Let $p \in \mathbb{Z} $, then $p$ is a \textbf{Prime Element} if \\  \begin{center}  when $p | a \cdot b$ then $p | a \vee p | b$.\\   \end{center}  Instead $p $ is a \textbf{Prime Number} if its only divisors are $1$ and $p$. In $\mathbb{Z}$ prime elements are all and only the prime numbers.\\  Two numbers $a$ and $b$ are \textbf{Relatively Primes} if $gcd(a,b)=1 $. \\ \ \\  We could observe that if $d=gcd(a,b)$ then $\exists x,y \in \mathbb{Z}$ such that $d=ax+by$ and this is called \textbf{Bezout Identity}.  Then given $x_{0},y_{0}$ such that $ax_{0}+by_{0}=d$ then every other solution $x,y$ is of the form:  $$x= x_{0} + \dfrac{b \cdot k}{d}, \ \ \ \ \ \ \ \ \ \ \ \ \ y= y_{0} - \dfrac{a\cdot k}{d} \ \ \ \ \ \ \ \ k \in \mathbb{Z} $$.  In particular if $a$ and $b$ relatively primes $\exists x,y \in \mathbb{Z}$ such that $ax+by=1$.  To find the Bezout Identity we could use the Euclidean Algorithm and then write the last remainder with $a$ and $b$ as in the following example:\\  $a=27, b=21$ \\  \begin{flushleft}  \begin{equation}  \begin{split}  &27=21 \cdot 1+6 \\   &21=6 \cdot 3 +3 \\  &6= 3 \cdot 2 + 0 \\  &gcd(27,21)=3 \\  \ \\  &6=27 \cdot 1 + 21 \cdot (-1) \\  &21 \cdot 1 = 27 \cdot 3 + 21 \cdot (-3) + 3 \ \ \Rightarrow 3 = 27 \cdot (-3) + 21 \cdot 4 \\  \end{split}   \end{equation}  \end{flushleft}  The role of the prime numbers is very important to study the cryptographic problems.  \\  \section{Modular Arithmetic}  Let's define over $\mathbb{Z}$ an Equivalence Relation, the Congruence Modulo $m$, denoted by $\equiv_{m}$ with $m \in \mathbb{N}$.Two numbers $a$ and $b$ are congruent modulo $m$ if and only if $m |(a-b)$ :  $$a \equiv_{m} b \ \ \Leftrightarrow m | (a-b).$$  Obviously the multiples of $m$ are congurent $0$ modulo $m$ because:   $$\forall k\in \mathbb{Z } \ \ \ \ m|k\cdot m =(k \cdot m -0) \ \Leftrightarrow k\cdot m \equiv_{m} 0$$   We could consider the quotient set $\mathbb{Z}_{/ \equiv_{m}}$ that we could denote as $\mathbb{Z}_{m}$ and this is the set of the non negative numbers that are strictly less than $m$:  $$\forall a \in \mathbb{Z} \ \ \ \ a= q \cdot m + r \ \ \ \ 0 \leq r < m \ \ \ a\equiv_{m} 0 + r = r \ and \ 0 \leq r < m$$  so e.g.:\ \\  \begin{center}  $\mathbb{Z}_{2}=\lbrace 0_{2},1_{2} \rbrace $ \ \\  $\mathbb{Z}_{5}=\lbrace 0_{5},1_{5},2_{5},3_{5}, 4_{5} \rbrace $  \end{center}