abordaremos as relações entre múltiplos e divisores no conjunto dos números inteiros, e conceitos como aritmética dos restos, divisão euclidiana, fatoração, entre outros, que são base de uma tecnologia que, apesar de ser largamente utilizada, é pouco visível, a criptografia de chave pública RSA.
Criptografia RSA
embora a descrição completa do funcionamento do método RSA de criptografia não seja contemplado neste texto, o objetivo é apresentar os conceitos sobre os quais o método foi desenvolvido. de forma simples o RSA envolve um par de chaves, uma pública e outra privada, que são formadas a partir do produto de dois primos:
$$n = p.q$$
onde \(n\) é a chave pública e o par \(p\) e \(q\) a chave privada. para encriptar a mensagem usamos \(n=p.q\) , para decodificar usamos \(p\) e \(q\) e a segurança do método reside na dificuldade de fatorar dois primos de muitos algarismos. obviamente há muitos outros conceitos e teoremas que sustentam a inviolabilidade da criptografia de chave pública, como a proposição 20 dos Elementos de Euclides de que existem infinitos números primos, mas como a proposta aqui é instigar a curiosidade, deixaremos os tópicos mais abstratos para mais tarde e focaremos nas propriedades mais básicas dos inteiros.
Divisibilidade no conjunto dos inteiros
a definição da relação de divisibilidade nos diz que, sejam \(a\) e \(b\) números inteiros, dizemos que \(a\) é divisor de \(b\) se, e somente se, existe um número natural \(n\) tal que \(b=a.n\). a expressão “\(a\) é divisor de \(b\)“ pode ser anotado por \(a\mid b\), que é diferente de \(a\div b\) já que estamos trabalhando no conjunto dos números inteiros, quando “\(a\) não divide \(b\)“ anota-se \(a\nmid b\). então:
$$(\forall\ a,b\ \in\ \mathbb{Z})\ (a\mid b \Leftrightarrow \exists \ \in \mathbb{Z} : b=a.n)$$
a sentença acima nos diz que \(n\) também é um divisor de \(b\), ou seja quando identificamos um divisor de um número inteiro, estamos na verdade identificando dois deles. dizer que \(a\) é divisor de \(b\) é equivalente a dizer que \(b\) é um múltiplo de \(a\).
Algoritmo da Divisão em \(\mathbb{Z}\)
chamado também algoritmo de Euclides ou divisão euclidiana, o algoritmo da divisão se apresenta como um teorema:
sejam \(a\) e \(b\) números inteiros com \(b\ne0\); então existe um único par de números inteiros \(q\) e \(r\) de modo que \(a=b.q+r\), com \(0\le r < |b|\).
novamente como ocorre na divisibilidade, não estamos tratando aqui da operação divisão, mas sim da relação entre dois inteiros.
Congruência módulo \(m\)
uma outra relação entre inteiros é a de congruência, que é estreitamente ligada a relação de divisibilidade em \(\mathbb{Z}\). pela definição, sejam \(a\), \(b\) e \(m\) números inteiros com \(m >1\), \(a\) é côngruo \(b\) módulo \(m\), se e somente se, \(m\) é um divisor de \(a-b\).
$$a\equiv b\pmod m \iff m\mid(a-b)$$
dessa forma, se usarmos o algoritmo da divisão, teremos \(a-b=m.k\), com \(k \in \mathbb{Z}\).
propriedades:
- sejam \(a, b, c, d\ e\ m \in \mathbb{Z}\ com\ m>1.\) se \(a\equiv b\pmod m\) e \(c\equiv d\pmod m\), temos:
$$
\begin{align}
(a+c) &\equiv (b+d) &\pmod{m} \\
(a-c) &\equiv (b-d) &\pmod{m} \\
a \cdot c &\equiv b \cdot c &\pmod{m} \\
a^n &\equiv b^n &\pmod{m}, \quad \forall n \geq 1
\end{align}
$$ - sejam \(a, b, c, d\ e\ m \in \mathbb{Z}, m>1\). então \(a\equiv b\pmod m\), se e somente se, \(a\) e \(b\) tem o mesmo resto na divisão euclidiana por \(m\).
descubra muitíssimo mais no livro do professor coutinho e em breve alguns exercícios usando python
Deixe um comentário