NÚMEROS PRIMOS

Um número é denominado primo se for um inteiro maior que 1 e cujos únicos fatores (divisores inteiros) são o 1 e ele mesmo. Exemplos dos primeiros números primos são 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29.

Obs.: Os números que têm mais de dois fatores são denominados números compostos. O número 1 não é primo nem composto.

 

História

Embora haja indícios de conhecimento pelos egípcios, o primeiro registro histórico de estudos com os números primos é do matemático grego Euclides (300 aC). Ele validou o conceito de que não existe um limite para os números primos. Ele provou em seu teorema que para cada número primo, por exemplo p, existe um número primo p’ que é maior que p.

Ainda na antiguidade, Eratóstenes, matemático e geógrafo grego (275-194 aC). Ele desenvolveu um método para encontrar os números primos de uma lista de números naturais. Esse método é utilizado até hoje e se chama ‘peneira’ ou ‘crivo’ de Eratóstenes.

 

Utilização

Os números primos são utilizados na determinação de Mínimos Múltiplos Comuns (MMC) e Máximos Divisores Comuns (MDC). De acordo com o teorema da fatoração, todo número inteiro positivo maior que um pode ser decomposto em fatores primos.

Os números primos são muito utilizados em processos de criptografia, tais como o RSA (fatoração do produto de número primos) e Diffie-Hellman (protocolo de troca de chaves com números primos), pois podem ser muito úteis para criar chaves mais difíceis de serem descobertas, pois não são fatoráveis. Os algoritmos Diffie-Hellman e esquemas de criptografia DSS (Digital Signature Standard ), no entanto, são frequentemente padronizados e usados ​​por um grande número de aplicativos.

 

Como determinar se um número é primo?

Liste os números inteiros em uma faixa (por ex. de 1 a 100). A partir do 2, o primeiro número primo, elimine os múltiplos de cada número primo em ordem crescente (2, 3, 5, 7 …) até que só tenhamos os números primos. Esse método é semelhante ao utilizado na ‘peneira’ ou ‘crivo’ de Eratóstenes.

Existem ainda fórmulas matemáticas que não são 100% confiáveis, tais como: 6 x n +1 e -1, onde n é um número natural; e n² + n + 41, onde n = 0, 1, 2, 3… 39.

Para números muito grandes verifique se o mesmo termina em 0, 2, 4, 5, 6 e 8. Neste caso, não pode ser primo, pois é múltiplo de 2 e/ou 5. Caso contrário, verifique se a soma dos dígitos é um múltiplo de 3, pois nesse caso o número será múltiplo de 3. Por fim, ache a raiz quadrada do número e então divida o número por todos os números primos até o valor da raiz quadrada. Se não for divisível por algum deles é primo.

 

Referências:

Teoria de números/Números primos, https://pt.wikibooks.org/w/index.php?title=Teoria_de_n%C3%BAmeros/N%C3%BAmeros_primos&oldid=452398 (visitado em 16 de setembro de 2022).

Renato Santino – Entenda por que os números primos são importantes nos dias atuais – 21/01/2016 22h25 – https://olhardigital.com.br/2016/01/21/seguranca/entenda-por-que-os-numeros-primos-sao-importantes-nos-dias-atuais/, acessado em 16/09/2022.

Manoel Lemos – Criptografia, Números Primos e Algoritmos – 4ª edição – Universidade Federal de Pernambuco – https://impa.br/wp-content/uploads/2017/04/PM_04.pdf, acessado em 16/09/2022.

Carlos Maziero, Seguranca¸ Computacional – 2019 – http://wiki.inf.ufpr.br/maziero/lib/exe/fetch.php?media=sc:seg-texto-03.pdf, acessado em 16/09/2022.