Um número primo é um número inteiro maior que 1, cujos únicos factores são 1 e ele próprio. Um fator é um número inteiro que pode ser dividido igualmente em outro número. Os primeiros números primos são 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. Números que têm mais de dois fatores são chamados de números compostos. O número 1 não é prime nem composite.
Números prime podem ser usados por uma série de razões. Por exemplo, alguns tipos de criptografia usam números primos.
Para cada número primo, por exemplo "p", existe um número primo que é maior que p, chamado p'. Esta prova matemática, que foi demonstrada em tempos antigos pelo matemático grego Euclid, valida o conceito de que não existe um número primo "maior". Como o conjunto de números naturais N = {1, 2, 3, ...} prossegue, os números primos geralmente tornam-se menos frequentes e são mais difíceis de encontrar num período de tempo razoável.
Como determinar se um número é primo
Um computador pode ser usado para testar números extremamente grandes para ver se eles são primos. Mas, como não há limite para o tamanho de um número natural, há sempre um ponto em que testar desta forma torna-se uma tarefa demasiado grande -- mesmo para os mais poderosos supercomputadores. Como exemplo, o maior número primo conhecido em dezembro de 2018 era 24.862.048 dígitos.
Vários algoritmos foram formulados na tentativa de gerar números primos cada vez maiores. Por exemplo, suponha "n" é um número inteiro, e ainda não se sabe se n é prime ou composto. Primeiro, pegue a raiz quadrada -- ou a potência 1/2 -- de n; depois arredonde este número para o próximo número inteiro mais alto e chame o resultado m. depois encontre todos os seguintes quocientes:
qm = n / m
q(m-1) = n / (m-1)
q(m-2) = n / (m-2)
q(m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2
O número n n é primo se -- e apenas se -- nenhum dos q's, como derivados acima, são números inteiros.
<Mersenne e Fermat primes
A Mersenne prime é um número que deve ser redutível à forma 2 n - 1, onde n é um número prime. Os primeiros poucos valores conhecidos de n que produzem primes Mersenne são onde n = 2, n = 3, n = 5, n n = 7, n = 13, n = 17, n = 19, n = 31, n = 61, e n n = 89.
A Fermat prime é um número Fermat que também é prime. Um número Fermat F n é da forma 2 m + 1, onde m m significa o potência de 2 -- isto é, m = 2 n, e onde n é um inteiro.
Números primos e criptografia
Criptografia segue sempre uma regra fundamental: o algoritmo -- ou o procedimento real a ser usado -- não precisa ser mantido em segredo, mas a chave sim. Prime numbers pode ser muito útil para criar key. Por exemplo, a força do criptografia de chave pública/privada reside no fato de que é fácil calcular o produto de dois números primos escolhidos aleatoriamente. Entretanto, pode ser muito difícil e demorado determinar quais dois números primos foram usados para criar um produto extremamente grande, quando apenas o produto é conhecido.
Na RSA (Rivest-Shamir-Adleman), um exemplo bem conhecido de criptografia de chave pública, os números primos são sempre supostos serem únicos. Os primes usados pelo Diffie-Hellman key exchange e os esquemas de criptografia Digital Signature Standard (DSS), no entanto, são frequentemente padronizados e usados por um grande número de aplicações.