Pseudoprime - Pseudoprime
Um pseudoprime é um primo provável (um inteiro que compartilha uma propriedade comum a todos os números primos ) que não é realmente primo. Os pseudoprimos são classificados de acordo com as propriedades dos primos que eles satisfazem.
Algumas fontes usam o termo pseudoprime para descrever todos os primos prováveis, tanto os números compostos quanto os primos reais.
Os pseudoprimos são de importância primária na criptografia de chave pública , que aproveita a dificuldade de fatorar grandes números em seus fatores primos. Carl Pomerance estimou em 1988 que custaria $ 10 milhões para fatorar um número com 144 dígitos e $ 100 bilhões para fatorar um número de 200 dígitos (o custo hoje é drasticamente menor, mas ainda proibitivamente alto). Mas encontrar dois grandes números primos conforme necessário para esse uso também é caro, portanto, vários testes de primalidade probabilísticos são usados, alguns dos quais, em casos raros, fornecem números compostos em vez de primos de maneira inadequada. Por outro lado, os testes de primalidade determinísticos, como o teste de primalidade AKS , não dão falsos positivos ; não há pseudoprimos com respeito a eles.
Pseudoprimas de Fermat
O pequeno teorema de Fermat afirma que se p é primo e a é coprime de p , então a p −1 - 1 é divisível por p . Para um inteiro a > 1, se um inteiro composto x divide a x −1 - 1, então x é chamado de pseudoprima de Fermat para basear a . Segue-se que se x é um pseudoprima de Fermat com base em a , então x é coprime com a . Algumas fontes usam variações desta definição, por exemplo, para permitir que apenas números ímpares sejam pseudoprimos.
Um inteiro x que é um pseudoprime de Fermat para todos os valores de a que são coprimos ax é chamado de número de Carmichael .