Sequência de Números Primos — Importância e Eficiêcia de Métodos
Na revolução tecnico científica, conhecida como 3° revolução industrial, o acúmulo de dados se tornou algo comum em grandes empresas para se ter uma melhor margem de lucros. Contudo, algo que caminhou junto com isso foram os problemas de segurança, algo preocupante, principalmente, para empresas bancárias que trabalham baseadas na confiança dos clientes que suas informações estarão seguras e o dinheiro não será acessado indevidamente.
Com isso, desenvolver uma maneira segura de troca de informações por meio dos canais de comunicação é algo que se tornou necessário e teve que ser tratado com mais importância nessa era. Baseado nisso, foram criado várias maneiras de trazer essa segurança utilizando técnicas de criptografia dessas informações para torna-las de difícil acesso.
Das várias maneiras que existem de criptografia, o RSA é um método que se destaca, pois utiliza números primos de valores elevados para proporcionar segurança. Dentre os passoas desse algoritmo, ele utiliza dois números primos da ordem de 10¹⁰⁰. Um desses primos é uma chave pública, que está relacionada ao usuário, e outra é uma chave privada, que está relacionada ao admin do servidor principal. Esse dois primos, quando multiplicados, geram um número que será usado na criptografia e início do método. Para obter as informações do usuário, basta descriptografar, ou nesse caso fatorar, o número gerado nos dois primos originais.
O problema parece simples, mas na prática é extremamente custoso computacionalmente. Com isso, obter uma forma eficiente de fatorar esse número é o que o torna complexo, pois não há uma fórmula fechada para a sequência de números primos.
Matematicamente existe a possibilidade de ser obter uma fórmula para a sequência de primos se a Hipótese de Riemann para a função Zeta for provada, pois o resultado dessa hipótese resulta na distribuição dos números primos. Contudo, mesmo que seja possível, pelo Teorema de Euclides, existem infinitos números primos, então seria possível criar criptografias mais complexas com isso.
Atualmente, há várias maneiras de obter números primos, contudo a maioria delas é válida para apenas alguns intervalos de números. Outras obtêm todos os números primos na teoria, mas na prática é computacionalmente ineficiente devido ao custo das operações que se tornam altas com o aumento da ordem de grandeza dos números primos.
Uma forma clássica na matemática de obter sequências de números primos é a realizar iterações a partir de uma lista de numeros sequenciais e armazenar os que são primos, no qual a condição do número ser primo é que ele só pode ser divisível por 1 ou por ele mesmo. No fluxograma abaixo é mostrado de forma visual como seria possível obter sequência de primos a partir do método descrito.
Esse método é possui ordem de grandeza O(N²). Isso ocorre, pois para saber se um número é primo é feita uma iteração baseado nos primos anteriores, verificando divisões e avaliando o resto. No código abaixo é mais fácil verificar esse resultado, no qual na linha 8 mostra a iteração a mais. Na linha 9 é avaliado o resto.
Baseado nesse algoritmo é possível fazer algumas melhorias usando o métodos como a Peneira de Eratosthenes, que atua como um filtro e torna a linha 8 mais eficiente. Caso tenha interesse, vou deixar o link abaixo para ver o método.
Esse foi um texto um pouco longo, mas acredito que deve ter sido interessante. Caso tenha encontrado algum problema deixe um comentário que eu conserto. Valeu! 👋
