Número pseudoprimo: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Impugnado, já tem referências |
|||
Linha 1:
Um '''pseudoprimo''' é um [[número]] [[primo provável]] (um [[inteiro]] que partilha propriedades com os números [[primo|primos]]) que não é verdadeiramente primo. Pseudoprimos são classificados de acordo com a propriedade dos primos que satisfazem<ref>{{citar web|URL = http://primes.utm.edu/glossary/xpage/Pseudoprime.html|título = The Prime Glossary: pseudoprime|data = |acessadoem = |autor = |publicado = }}</ref>. ▼
▲Um pseudoprimo é um [[primo provável]] (um [[inteiro]] que partilha propriedades com os números [[primo|primos]]) que não é verdadeiramente primo. Pseudoprimos são classificados de acordo com a propriedade dos primos que satisfazem<ref>{{citar web|URL = http://primes.utm.edu/glossary/xpage/Pseudoprime.html|título = The Prime Glossary: pseudoprime|data = |acessadoem = |autor = |publicado = }}</ref>.
Pseudoprimos têm importância primária na [[criptografia]] de chave pública, em algoritmos que utilizam números primos grandes em seu funcionamento, e em geral se baseiam no grande custo computacional de fatorar inteiros. Muitas vezes encontrar números primos grandes deterministicamente também é um problema de custo computacional elevado, e portanto podem ser usados [[teste de primalidade|testes de primalidade]] probabilísticos, que em raros casos dão falsos positivos, identificando números compostos como primos. Tais números são classificados como pseudoprimos em relação a este teste.
Linha 6 ⟶ 5:
== Pseudoprimo de Fermat ==
O [[pequeno teorema de Fermat]] afirma que se p é primo e a é coprimo com p, então <math>a^{p-1}-1</math> é divisível por p. Um inteiro composto n tal que n divide <math>a^{n-1}-1</math> é chamado pseudoprimo de Fermat na base a<ref>{{citar web|URL = http://mathworld.wolfram.com/FermatPseudoprime.html|título = Fermat Pseudoprime|data = |acessadoem = |autor = |publicado = }}</ref>. Segue do fato de que n é pseudoprimo na base a que n e a são coprimos. Um inteiro n pseudoprimo de Fermat na base a para todo a coprimo com n é chamado [[número de Carmichael]]<ref>{{citar web|URL = http://mathworld.wolfram.com/CarmichaelNumber.html|título = Carmichael Number|data = |acessadoem = |autor = |publicado = }}</ref>.
{{referências}}
{{Classes de números primos|estado=autocollapse}}
[[Categoria:Matemática]]
| |||