Números Pseudoprimos — Definição, Propriedades e Aplicações
O que são números pseudoprimos
Números pseudoprimos são números compostos que passam em certos testes de primalidade, “enganando” esses testes e sendo erroneamente classificados como primos.
Por exemplo, \(341\) é composto (\(341=11\cdot31\)), mas satisfaz a condição de Fermat para \(a=2\):
Tipos de pseudoprimos
- Pseudoprimos de Fermat: Compostos que passam no teste de Fermat para alguma base \(a\).
- Números de Carmichael: Compostos que passam no teste de Fermat para todas as bases coprimas.
- Pseudoprimos fortes: Resistentes a testes de primalidade mais rigorosos.
Propriedades e características
- Todo número primo passa no teste de Fermat para qualquer base coprima.
- Nem todo número que passa nesse teste é primo: pode ser pseudoprimo.
- Os números de Carmichael são um caso especial de pseudoprimos mais “fortes”.
Teste de primalidade de Fermat
O teste de Fermat verifica se um número \(n\) é possivelmente primo, testando se:
Se falhar, \(n\) é composto. Se passar, pode ser primo ou pseudoprimo para a base \(a\).
Exemplos resolvidos
Exemplo 1 — Pseudoprimo para base 2
Solução
O número \(341\) passa no teste de Fermat para \(a=2\), mas não é primo, pois \(341=11\cdot31\).
Exemplo 2 — Número de Carmichael
Solução
O número \(561\) é um exemplo clássico de número de Carmichael. Ele passa no teste de Fermat para todas as bases \(a\) coprimas a \(561\).
Aplicações em criptografia
Os pseudoprimos são importantes na criptografia moderna, especialmente em sistemas como RSA, que dependem de números primos grandes.
- Servem para testar a eficiência de algoritmos de primalidade.
- Fornecem base para sistemas criptográficos seguros.
Leituras relacionadas
Resumo e materiais
- ✔ Números pseudoprimos passam em testes de primalidade, mas não são primos.
- ✔ Conhecer suas propriedades é essencial para algoritmos criptográficos.
- ✔ Relação direta com números de Carmichael e pseudoprimos fortes.
