\chapter{Alguns conceitos matemáticos importantes}
	
	A cifra de Hill utiliza matrizes quadradas como modelo para a chave de
	cifragem, e vetores como modelo para os blocos de texto a serem cifrados. As
	operações da cifra de Hill são operações matriciais, que no fundo se resumem a
	operações com números. Os elementos das matrizes devem ser números inteiros
	pois o processo utiliza também de aritmética modular, uma operação que só faz
	sentido com inteiros, e será revisada na seção seguinte. Agora, porém, surge
	uma questão: Como \emph{associar} símbolos a números?
	
	\section{Função e Função Bijetora}
		
		A palavra \emph{associar} sugere o uso do conceito matemático de função. Uma
		função pode ser vista como uma \emph{regra} que associa cada elemento de um
		conjunto, chamado de domínio da função, a somente um elemento do outro conjunto,
		o contra-domínio. Para nossa necessidade, de associar letras a números, teremos
		uma função do tipo: $$ f: A \to \mathbb{Z}_n $$ onde A é um alfabeto qualquer
		(conjunto finito de símbolos), e $ \mathbb{Z}_n $ é o conjunto dos inteiros
		de 0 a n-1.
		
		\begin{description}
		
		\item[Exemplo 1:]
		Seja $f: A \to \mathbb{Z}_{26} $ onde A=\{alfabeto de 26 letras\} e
		Z=\{0,1,\ldots,25\} dada por:
		\begin{align*}
        	& a \mapsto 0 \\
			& b \mapsto 1 \\
			& c \mapsto 2 \\
		 	& \ldots \\
			& z \mapsto 25
        \end{align*}
		Para executar as operações da Cifra de Hill sobre um dado texto, precisamos
		aplicar uma função que leve de letras para inteiros não-negativos, mas se
		quisermos saber o "resultado" da cifragem, ou se quisermos decifrar uma mensagem
		cifrada usando o processo de Hill, precisamos \emph{inverter} essa função que
		leva para números, ou seja, precisamos de: $ f^{-1} : \mathbb{Z}_n \to A $, ou
		seja, precisamos da \emph{função inversa} de f. Invertendo a função do Exemplo 1,
		ficamos com:
		
		\item[Função inversa do Exemplo 1:]
		Tomando a função $ f^{-1} $ inversa de $f$, temos:
		\begin{align*}
        	& 0 \mapsto a \\
			& 1 \mapsto b \\
			& 2 \mapsto c \\
		 	& \ldots \\
			& 25 \mapsto z
        \end{align*}
		
		\end{description}
		
		Por definição, uma função qualquer f é inversível se e somente se ela for
		\emph{bijetora}, o que é sinônimo de um mapeamento um-para-um. Uma função dita
		bijetora, e portanto INVERSÍVEL, satisfaz duas condições:
		
		\begin{equation}  x \neq y  \longrightarrow  f(x) \neq f(y)  \end{equation}
		\begin{equation}  Im(f) = Contradom(f)  \end{equation}
		
		A primeira condição diz que elementos diferentes do domínio estão associados a
		elementos diferentes no contradomínio. A segunda condição diz que cada elemento
		do contradomínio deve ter um elemento do domínio associado a ele. A segunda
		condição também pode ser expressa da seguinte maneira (talvez mais explícita):
		$ \left|Dom(f)\right| = \left|Contradom(f)\right| $, ou seja, o domínio e o
		contradomínio devem ter o mesmo \emph{número} de elementos; não podem
		``sobrar'' elementos não associados.
		
		Se tivermos um texto fonte, e desejarmos criptografá-lo usando a Cifra de Hill,
		devemos então associar as \textit{n} letras do alfabeto aos inteiros de 0 até
		n-1. Não há nenhuma função específica que deva ser usada para fazer essa
		associação. Porém devemos ter certeza de que a função usada é inversível, para
		depois podermos realizar o processo inverso.
		
		
		
	\section{Aritmética Modular}
		Como já foi mencionado anteriormente, os métodos criptográficos - e em
		particular a Cifra de Hill - trabalham sobre \emph{alfabetos}, que são
		conjuntos FINITOS de símbolos. Associando esses símbolos a um conjunto de
		números podemos usar operações aritméticas úteis sobre estes números. Porém, ao
		usar uma cifra, nós queremos que ao final do processo encriptação - transmissão -
		decriptação nós tenhamos a mensagem no mesmo alfabeto do texto original.
		
		Assim, se fizermos a associação de letras com inteiros e chegarmos a um
		conjunto $ \mathbb{Z}_n $, devemos GARANTIR que todas as operações realizadas
		na cifragem (operações entre elementos desse conjunto $\mathbb{Z}_n$) resultem
		em elementos desse mesmo conjunto, ou seja, as operações devem ser
		\emph{fechadas}; só assim poderemos voltar à mensagem no alfabeto
		original. Essa garantia se obtém pelo uso da \emph{aritmética modular}.
		
		\subsection{Operação Módulo e congruência}
			Em várias situações, estamos interessados apenas no \emph{resto} da divisão
			entre dois inteiros. Um exemplo clássico é quando perguntamos: ``Que horas
			serão daqui a 30 horas'', nesse caso nos interessa apenas o resto de (50 + hora
			atual)/24. Existe uma operação binária entre inteiros, chamada \emph{módulo},
			definida da seguinte maneira:
			
			$$ a \bmod n = r  \Longrightarrow  a = qn + r $$
			
			Ou seja, \emph{a mod n} é o resto da divisão inteira de a por n. A operação
			módulo define uma relação muito útil sobre os inteiros, semelhante à igualdade:
			é a CONGRUÊNCIA. A relação de congruência é definida usando a operação módulo
			da seguinte maneira:
			
			$$ a \equiv b \pmod{n}  \Longleftrightarrow  a \bmod n = b \bmod n $$
			
			Ou seja, a é congruente a b módulo n se e somente se a e b tiverem o mesmo
			resto (módulo) quando divididos por n. A relação de congruência sobre os
			inteiros é a base que estrutura a aritmética modular. A aritmética modular foi
			desenvolvida pelo grande matemático Carl Friedrich Gauss e é o fundamento da
			teoria dos números. A aritmética modular tem muitas aplicações práticas,
			incluindo música, artes visuais, química, e sendo a criptografia uma das mais
			importantes. Vamos revisá-la com mais detalhes então.
			
		\subsection{Aritmética modular}
			A aritmética modular é um conjunto de operações que estão definidas (fazem
			sentido) somente para os números inteiros. Elas são semelhantes às operações
			usuais de adição e multiplicação, mas funcionam como se fossem operações
			``circulares'' em torno de um conjunto finito de inteiros de 0 a n-1. Para
			ilustrar melhor esse conceito intuitivo, voltemos ao exemplo do relógio:
			
			Suponha que sejam 4h da manhã. Nesse caso a pergunta: ``Que horas serão daqui a
			30h?'' (usando x como incógnita) equivale à seguinte expressão
			usando adição módulo 24:
			
			$$ 4 + 30 \equiv x \pmod{24} $$
			
			Ora, somando-se usualmente 30 e 4 obtemos 34, mas não usando uma adição
			módulo 24. Usando a adição modular nós temos:
			$ 4 + 30 \equiv x \pmod{24} \Longleftrightarrow x = (30 + 4) \bmod 24 $.
			Generalizando, uma \emph{adição módulo n} pode ser definida da seguinte forma:
			$$ a + b \equiv x \pmod{n}  \Longleftrightarrow  x = (a + b) \bmod n $$
			
			A mesma definição, apenas substituindo o símbolo da operação, vale para a
			multiplicação modualar. Enfim, há várias definições formais e complexas das
			operações da aritmética modular, mas para nossos propósitos basta a seguinte:
			\begin{description}
		
			  \item[Aritmética modular]
			  Realizar uma operação entre dois inteiros em \emph{aritmética modular} não é
			  nada mais do que primeiramente realizar a operação usual entre os inteiros
			  e, em seguida, tomar o resultado \emph{mod n}
			  
			\end{description}