this is for holding javascript data
Francesco Romeo Deleted File
about 8 years ago
Commit id: 70a0f886a08266433a9be183f500a379ff28938b
deletions | additions
diff --git a/Graduation Thesis.tex b/Graduation Thesis.tex
deleted file mode 100644
index bb764a2..0000000
--- a/Graduation Thesis.tex
+++ /dev/null
...
\chapter*{0. Mathematical Review}
\section{Elementary Set Theory}
\subsection{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 $\large\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. \ \\
\subsection{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.
\subsection{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$.
\subsection{Sets with Operations: Groups, Rings and Fields}
\subsubsection{$\dagger$ 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}
\subsubsection{$\dagger $ 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}.
\subsubsection{$\dagger$ 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}
\subsection{Number Sets: the Properties of $\mathbb{Z}$}
\subsubsection{$\dagger$ 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.
\subsubsection{$\dagger$ 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$.