{"id":99,"date":"2025-03-03T21:37:12","date_gmt":"2025-03-04T00:37:12","guid":{"rendered":"https:\/\/marinacaponerasilva.aztecweb.net.br\/?p=99"},"modified":"2025-03-25T23:52:05","modified_gmt":"2025-03-26T02:52:05","slug":"divisao-euclidiana-rsa","status":"publish","type":"post","link":"https:\/\/mcaponera.com.br\/index.php\/2025\/03\/03\/divisao-euclidiana-rsa\/","title":{"rendered":"rela\u00e7\u00f5es euclidianas e a criptografia"},"content":{"rendered":"\n
\n
\"ilustra\u00e7\u00e3o<\/figure><\/div>\n\n\n\n
\n
\n

abordaremos as rela\u00e7\u00f5es entre m\u00faltiplos e divisores no conjunto dos n\u00fameros inteiros<\/strong>, e conceitos como aritm\u00e9tica dos restos<\/strong>, divis\u00e3o euclidiana<\/strong>, fatora\u00e7\u00e3o<\/strong>, entre outros, que s\u00e3o base de uma tecnologia que, apesar de ser largamente utilizada, \u00e9 pouco vis\u00edvel, a criptografia de chave p\u00fablica RSA.<\/em><\/p>\n<\/blockquote>\n<\/div>\n<\/div>\n\n\n\n\n\n\n

Criptografia RSA<\/h3>\n\n\n\n

embora a descri\u00e7\u00e3o completa do funcionamento do m\u00e9todo RSA de criptografia n\u00e3o seja contemplado neste texto, o objetivo \u00e9 apresentar os conceitos sobre os quais o m\u00e9todo foi desenvolvido. de forma simples o RSA envolve um par de chaves, uma p\u00fablica e outra privada, que s\u00e3o formadas a partir do produto de dois primos:<\/p>\n\n\n\n

$$n = p.q$$<\/p>\n\n\n\n

onde \\(n\\) \u00e9 a chave p\u00fablica 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\u00e7a do m\u00e9todo reside na dificuldade de fatorar dois primos de muitos algarismos. obviamente h\u00e1 muitos outros conceitos e teoremas que sustentam a inviolabilidade da criptografia de chave p\u00fablica, como a proposi\u00e7\u00e3o 20 dos Elementos<\/em> de Euclides de que existem infinitos n\u00fameros primos, mas como a proposta aqui \u00e9 instigar a curiosidade, deixaremos os t\u00f3picos mais abstratos para mais tarde e focaremos nas propriedades mais b\u00e1sicas dos inteiros.<\/p>\n\n\n\n

Divisibilidade no conjunto dos inteiros<\/h2>\n\n\n\n

a defini\u00e7\u00e3o da rela\u00e7\u00e3o de divisibilidade nos diz que, sejam \\(a\\) e \\(b\\) n\u00fameros inteiros, dizemos que \\(a\\) \u00e9 divisor de \\(b\\) se, e somente se, existe um n\u00famero natural \\(n\\) tal que \\(b=a.n\\). a express\u00e3o “\\(a\\) \u00e9 divisor de \\(b\\)“<\/em> pode ser anotado por \\(a\\mid b\\), que \u00e9 diferente de \\(a\\div b\\) j\u00e1 que estamos trabalhando no conjunto dos n\u00fameros inteiros, quando “\\(a\\) n\u00e3o divide \\(b\\)“<\/em> anota-se \\(a\\nmid b\\). ent\u00e3o:<\/p>\n\n\n\n

$$(\\forall\\ a,b\\ \\in\\ \\mathbb{Z})\\ (a\\mid b \\Leftrightarrow \\exists \\ \\in \\mathbb{Z} : b=a.n)$$<\/p>\n\n\n\n

a senten\u00e7a acima nos diz que \\(n\\) tamb\u00e9m \u00e9 um divisor de \\(b\\), ou seja quando identificamos um divisor de um n\u00famero inteiro, estamos na verdade identificando dois deles. dizer que \\(a\\) \u00e9 divisor de \\(b\\) \u00e9 equivalente a dizer que \\(b\\) \u00e9 um m\u00faltiplo de \\(a\\).<\/p>\n\n\n\n

Algoritmo da Divis\u00e3o em \\(\\mathbb{Z}\\)<\/h3>\n\n\n\n

chamado tamb\u00e9m algoritmo de Euclides ou divis\u00e3o euclidiana, o algoritmo da divis\u00e3o se apresenta como um teorema:<\/p>\n\n\n\n

\n

sejam \\(a\\) e \\(b\\) n\u00fameros inteiros com \\(b\\ne0\\); ent\u00e3o existe um \u00fanico par de n\u00fameros inteiros \\(q\\) e \\(r\\) de modo que \\(a=b.q+r\\), com \\(0\\le r < |b|\\).<\/p>\n<\/blockquote>\n\n\n\n

novamente como ocorre na divisibilidade, n\u00e3o estamos tratando aqui da opera\u00e7\u00e3o divis\u00e3o, mas sim da rela\u00e7\u00e3o entre dois inteiros.<\/p>\n\n\n\n

Congru\u00eancia m\u00f3dulo \\(m\\)<\/h3>\n\n\n\n

uma outra rela\u00e7\u00e3o entre inteiros \u00e9 a de congru\u00eancia, que \u00e9 estreitamente ligada a rela\u00e7\u00e3o de divisibilidade em \\(\\mathbb{Z}\\). pela defini\u00e7\u00e3o, sejam \\(a\\), \\(b\\) e \\(m\\) n\u00fameros inteiros com \\(m >1\\), \\(a\\) \u00e9 c\u00f4ngruo \\(b\\) m\u00f3dulo \\(m\\), se e somente se, \\(m\\) \u00e9 um divisor de \\(a-b\\).<\/em><\/p>\n\n\n\n

$$a\\equiv b\\pmod m \\iff m\\mid(a-b)$$<\/p>\n\n\n\n

dessa forma, se usarmos o algoritmo da divis\u00e3o, teremos \\(a-b=m.k\\), com \\(k \\in \\mathbb{Z}\\).<\/p>\n\n\n\n

propriedades<\/strong>:<\/p>\n\n\n\n