deletions | additions       diff --git a/chapter_0_Mathematical_Review_Elementary__.tex b/chapter_0_Mathematical_Review_Elementary__.tex  index bf5cae5..2b4565d 100644  --- a/chapter_0_Mathematical_Review_Elementary__.tex  +++ b/chapter_0_Mathematical_Review_Elementary__.tex 
...
\end{split}   \end{equation}  \end{flushleft}  The role So we could research the integer solutions  of the prime numbers is very important to study following equation  $$ax+by=c $$  that it's called \textbf{Diophantine Equation}. It's clear that it has integer solutions iff $gcd(a,b)|c$ and the solutions are the ones above found for  the cryptographic problems. Bezout Identity  \  \\ \section{Modular Arithmetic}  \subsection{Introduction of $\mathbb{Z}_{m}$ and $\mathbb{F}_{p} $}  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:  
...
\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} \ \\  We will prove that $\forall m \in \mathbb{N}, \ \ \ \mathbb{Z}_{m} $ is a \textbf{Ring} with the two operations $(+,\cdot)$ defined by:  $$If \ \ a \equiv_{m} c \ \ and \ \ \ b \equiv_{m} d \ \ \Rightarrow \ \ a+b \equiv_{m} c+d \ \ \ and \ \ \ a \cdot b \equiv_{m} c\cdot d $$  Obviously $(\mathbb{Z}_{m},+ )$ is an Abelian Group and $\cdot$ is associative commutative and the unit is $1_{m}$. But it's not ever possible to find the multiplicative inverse of an element. E.g.: \\  In $\mathbb{Z}_4 $ there is not inverse for $2_{4}$ in other words the equation  $$2\cdot x \equiv_{4} 1 $$  has not solution and this is because we coukld write it as  $$2\cdot x+4\cdot l = 1 $$  and this Diophantine Equation has not solution because $gcd(2,4)=2 \not\vert \ 1$. \\   Referring to the example above, we could say that $$a \ has \ inverse \ modulo \ m \ \ \Leftrightarrow \ \ gcd(a,m)=1$$  \ \\  We call $\mathbb{Z}_{m}^{*} $ the set of the elements that have multiplicative inverse:  $$\mathbb{Z}_{m}^{*}=\lbrace a \in \mathbb{Z}_{m} : a\cdot x \equiv_{m} 1 \ has \ solution \rbrace$$  and this is called the \textbf{Group of the Units} modulo $m$.  \ \\  If we take $m=p$ prime, every non-zero element has mutliplicative inverse then $\mathbb{Z}_{p}$ is a \textbf{Field} and we will call it $\mathbb{F}_{p}$; obviously $\mathbb{F}_{p}^{*}=\mathbb{F}_{p} \setminus \lbrace 0_{p} \rbrace$  \subsection{Fast Powering Algorithm}  It could be necessary to compute large powers of a number $g$ modulo another number $N$. This is possible by using the \textbf{Fast Powering Algorithm}. \\  Let $N \in \mathbb{N} $ , $g \in \mathbb{Z}_{N}$, $A \in \mathbb{N}$ a large number, we would compute:$$g^{A} \ mod \ N$$  First of all we write the binary expansion of $A$ (we write $A$ as sum of the powers of $2$):  $$A=A_{0}+A_{1} \cdot 2+A_{2} \cdot 2^{2}+\ldots + A_{r} \cdot 2^{r} \ \ \ \ \ \ \ \ \ \ \ A_{i} \in \lbrace 0,1 \rbrace, \ \ A_{r}=1$$  then   $$g^{A}=g^{A_{0}+A_{1} \cdot 2+A_{2} \cdot 2^{2}+\ldots + A_{r} \cdot 2^{r}}=g^{A_{0}} \cdot g^{A_{1} \cdot 2} \cdot g^{A_{2} \cdot 2^{2}} \cdot \ldots \cdot g^{A_{r} \cdot 2^{r}} $$  Now we take the powers $g^{2^{i}}, i=1, 2, \ldots, r$:  $$a_{0} \equiv g \ mod \ N$$  $$a_{1} \equiv a_{0}^2 \equiv g^{2} \ mod \ N$$  $$a_{2} \equiv a_{1}^2 \equiv g^{2^{2}} \ mod \ N $$  $$a_{3} \equiv a_{2}^2 \equiv g^{2^{3}} \ mod \ N $$  $$\vdots $$  $$a_{r} \equiv a_{r-1}^2 \equiv g^{2^{r}} \ mod \ N $$  Each term is the sqaure of the previous one, so this step requires $r$ multiplication.  Then   $$g^{A_{0}} \cdot g^{A_{1} \cdot 2} \cdot g^{A_{2} \cdot 2^{2}} \cdot \ldots \cdot g^{A_{r} \cdot 2^{r}} \equiv a_{0}^{A_{0}} \cdot a_{1}^{A_{1}} \cdot a_{2}^{A_{2}} \cdot \ldots \cdot a_{r}^{A_{r}} \ mod \ N $$  This step requires at the most $r$ multiplication and so the whole method's time is $2r$ multiplications.  We said that $A=A_{r} \cdot 2^{r}+ \ldots$ so we could say that $2^{r} \leq A < 2^{r+1}$ then $$2r \approx 2\log_{2}A$$  and if we consider $A \approx 2^{1000}$ this algorithm will take about 2000 steps to finish, instead of $A$ steps if we compute $g^{A}$ as $g \cdot g \cdot g \cdot \ldots \cdot g$,$A$ times.  \subsection{Euler's phi function and Fermat's Little Theorem}  Let $m \in \mathbb{N}$, we will call $\phi (m)$ the \textbf{Euler's phi function}, defined by:  $$\phi (m)= \sharp \mathbb{Z}_{m}^{*} = \sharp \lbrace a \in \mathbb{Z}_{m} : gcd(a,m)=1 \rbrace$$  So this function gives us the number of elements that are relatively prime with $m$.   If $p$ is prime, then $\phi (p)=p-1$ because every non-zero element is relatively prime with $p$.  \ \\  Now we want to study the powers of elements in $\mathbb{F}_{p}$ and we introduce this important result, called \textbf{ Fermat's Little Theorem}:  \begin{thm}[Fermat's Little Theorem]\ \\  Let $p$ be a prime, $a \in \mathbb{N}$ \ \\$$THEN$$ \ \\ $$a^{p-1} \equiv_{p} \begin{cases} 1 \ \ \ if \ \ p \not\vert \ a \\ 0 \ \ \ if \ \ p \ \vert \ a \end{cases} $$  \end{thm}  An immediate example is given by :  $$p=5,a=2 \ \ \ 2^{4}= 16 \equiv_{5} 1 $$  In Group theory we could introduce the notion of \textbf{Multiplicative Order} of elements and in $\mathbb{F}_{p}$ we could define it in this way:\\  Let $p$ be a prime, an element $a$ has \textbf{Multiplicative Order} $k$, if it's the smallest number such that  $$a^{k} \equiv_{p} 1$$  By the FLT, it's clear that $k \leq p-1$ and in particular $k | p-1$.  \\  A quick generalization of FLT, when the modulus is not prime is given by the \textbf{Fermat-Euler Theorem}:  \begin{thm}[Fermat-Euler Theorem]\ \\  Let $m,a \in \mathbb{N}$ \ \\ $$THEN$$ \ \\ $$a^{\phi (m)} \equiv_{m} \begin{cases} 1 \ \ \ if \ \ m \not\vert \ a \\ 0 \ \ \ if \ \ m \ \vert \ a \end{cases} $$  \end{thm}  and this is an important result when we aren't in $\mathbb{F}_{p}$.  \ \\  \subsection{Primitive Roots in $\mathbb{F}_{p}$}  If we take a small prime, e.g. $11$, and we take in $\mathbb{F}_{11}$ the element $2$ and its powers up to $2^{10}$:   $$ 2, \ 2^{2} \equiv_{11} 4, \ 2^{3} \equiv_{11} 8,\ 2^{4} \equiv_{11} 5,\ 2^{5} \equiv_{11} 10,\ 2^{6} \equiv_{11} 9,\ 2^{7} \equiv_{11} 7,\ 2^{8} \equiv_{11} 3,\ 2^{9} \equiv_{11} 6,\ 2^{10} \equiv_{11} 1$$  We could observe that the $2$ generates $\mathbb{F}_{11}^{*}$ then we will call it \textbf{Primitive Root} modulo 11.  \begin{defn}[Primitive Root]  Let $p$ be a prime, an element $g \in \mathbb{F}_{p}^{*} $ is a \textbf{Primitive Root} modulo $p$ if  $$\mathbb{F}_{p}^{*}= \lbrace 1,g,g^{2},\cdots,g^{p-2}\rbrace $$  \end{defn}  The number of Primitive Roots it's simple to find because it's $\phi (p-1)$ and finding one of them, e.g. $g$, the powers of $g$ whose exponent is relatively prime with $p-1$ are the other primitive roots.  \subsection{Equations in $\mathbb{F}_{p}$ : Chinese Remainder Theorem}  In $\mathbb{F}_{p}$ we could consider linear equations of the form:  $$a \cdot x \equiv_{p} b $$  To solve it we could consider $a^{-1} \ mod \ p$ and the solution is $$x \equiv_{p} a^{-1} \cdot b$$. To find the multiplicative inverse of $a$ we use the Euclidean Algorithm that takes about $\log p$ steps and this is the time to solve that equation.  But the problem could be to find a number satisfying a system of equations in $\mathbb{F}_{p}$ and the solution at this problem is given by the \textbf{Chinese Remainder Theorem}:  \begin{thm}[Chinese Remainder Theorem]  We consider the following system of equations:  $$ \begin{cases}  x \equiv r_{1} \ \ ( \ mod \ m_{1} \ ) \\  x \equiv r_{2} \ \ ( \ mod \ m_{2} \ ) \\  \vdots \\  x \equiv r_{n} \ \ ( \ mod \ m_{n}\ ) \\  \end{cases}$$  with $\forall i=1,\ldots,n \ \ m_{i} \in \mathbb{N}, \ \ r_{i} \in \mathbb{Z}_{m_{i}}$ and $\forall i \neq j \ \ gcd(m_{i},m_{j})=1$ \\  $$THEN$$ $\exists ! \ x $ solution modulo $m_{1} \cdot m_{2} \cdot \ldots \cdot {m_{n}}$  \end{thm}  This Theorem is Chinese because grouping soldiers two by two, three by three and taking the remainders the generals could count soldiers.  \section{Other Important Results}  \begin{itemize}  \item \textbf{Mathematical Induction}\\  It could be interesting knowing how to prove some results in $\mathbb{N}$ by using the \textbf{Principle of Induction}.  It says that given a preposition depending $n$ $P(n), \ \ \ n\in \mathbb{N}$, we could verify if it's true $\forall n \in \mathbb{N}$ in two steps:  \begin{enumerate}  \item \textbf{Basis} \\  We prove that the statement holds for the first natural number $n_{0}$ called \textbf{Basis of Induction}  \item \textbf{Inductive Step} \\  We prove that if $P(n)$ it's true then $P(n+1)$ is true  \end{enumerate}  \item \textbf{Lagrange's Theorem (Group Theory)}  \begin{thm}[Lagrange's Theorem (Group Theory)]  Let $G$ be a group, $H$ a subgroup of $G$, then $$\sharp H \ | \ \sharp G $$  \end{thm}  \ \\  So the order (number of elements ) of a subgroup $H$ divides the order of the Group.\\  An important consequence of this result is that the multiplicative order of the elements of a group divides the order of the group.  This is a quick proof of the FLT because the order of $\mathbb{F}_{p}^{*}$ is $p-1$, then the multiplicative order of every elements divides $p-1$ and $\forall a \in \mathbb{F}_{p}^{*} \ \ \ a^{p-1} \equiv_{p} 1 $  \end{itemize}