Número primo

Como encontrar pequenos números primos

Há um método simples para encontrar uma lista de números primos. Eratóstenes o criou. Ele tem o nome de Peneira de Eratóstenes. Ele captura números que não são números primos (como uma peneira) e deixa passar os números primos.

O método funciona com uma lista de números, e um número especial chamado b que muda durante o método. Ao percorrer o método, você circula alguns números na lista e risca outros. Cada número circulado é principal e cada número riscado é composto. No início, todos os números são simples: não circulados e não riscados.

O método é sempre o mesmo:

1. Em uma folha de papel, escreva todos os números inteiros, desde 2 até o número que está sendo testado. Não escreva o número 1. Vá para o próximo passo.
2. Comece com b igual a 2. Vá para o próximo passo.
3. Círculo b na lista. Vá para o próximo passo.
4. A partir de b, conte b mais na lista e risque esse número. Repita a contagem de b mais números e risque os números até o final da lista. Vá para o próximo passo.
• (Por exemplo: Quando b for 2, você fará um círculo 2 e riscará 4, 6, 8, e assim por diante. Quando b for 3, você fará um círculo 3 e riscará 6, 9, 12, e assim por diante. Os 6 e 12 já foram riscados. Risque-os novamente).
5. Aumentar b em 1. vá para o próximo passo.
6. Se b tiver sido riscado, volte ao passo anterior. Se b é um número da lista que não foi riscado, volte para a terceira etapa. Se b não estiver na lista, vá para a etapa final.
7. (Esta é a etapa final.) Você está feito. Todos os números primos são circulados e todos os números compostos são riscados

Como exemplo, você poderia fazer este método em uma lista dos números de 2 a 10. No final, os números 2, 3, 5, e 7 acabarão circulando. Eles são números primos. Os números 4, 6, 8, 9 e 10 serão riscados. Eles são números compostos.

Este método ou algoritmo leva muito tempo para encontrar números primos muito grandes. Mas é menos complicado do que os métodos usados para primas muito grandes, como o teste de primalidade de Fermat (um teste para ver se um número é primo ou não) ou o teste de primalidade de Miller-Rabin.

Para que números primos são usados

Os números primos são muito importantes em matemática e ciência da computação. Alguns usos do mundo real são dados abaixo. Números muito longos são difíceis de resolver. É difícil encontrar seus principais fatores, portanto, na maioria das vezes, os números que são provavelmente primos são usados para criptografia e códigos secretos.

• A maioria das pessoas tem um cartão bancário, onde elas podem obter dinheiro de sua conta, usando um caixa eletrônico. Este cartão é protegido por um código de acesso secreto. Como o código precisa ser mantido em segredo, ele não pode ser armazenado em texto claro no cartão. A encriptação é usada para armazenar o código de forma secreta. Esta criptografia utiliza multiplicações, divisões e encontrar restos de grandes números primos. Um algoritmo chamado RSA é freqüentemente usado na prática. Ele usa o teorema do restante chinês.

• Se alguém tem uma assinatura digital para seu e-mail, a criptografia é utilizada. Isto garante que ninguém possa falsificar um e-mail deles. Antes de assinar, é criado um valor hash da mensagem. Isto é então combinado com uma assinatura digital para produzir uma mensagem assinada. Os métodos usados são mais ou menos os mesmos que no primeiro caso acima.

• Encontrar o maior auge conhecido até agora se tornou uma espécie de esporte. Testar se um número é o prime pode ser difícil, se o número for grande. Os maiores primes conhecidos a qualquer momento são geralmente primes Mersenne porque o teste mais rápido conhecido para a primalidade é o teste Lucas-Lehmer, que se baseia na forma especial dos números Mersenne. Um grupo que busca primas Mersenne está aqui[1].