Número semiprimo

Em matemática, um número semiprimo (também chamado biprimo ou 2-quasi-primo, ou número pq), é um número natural que é o produto de dois números primos, não necessariamente distintos. Os primeiros semiprimos são 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, ... (sequência A001358 na OEIS).

Até março de 2011, o maior semiprimo conhecido era (2^43,112,609 − 1)², com mais de 25 milhões de dígitos. Esse número é o quadrado do maior número primo conhecido. O quadrado de qualquer número primo é semiprimo, e o maior semiprimo conhecido será sempre o quadrado do maior primo conhecido, a menos que os fatores do semiprimo não sejam conhecidos. É concebível que poderia ser encontrada uma forma de se provar que um número maior é um semiprimo sem conhecer os dois fatores, mas isso ainda não aconteceu com os maiores semiprimos encontrados até o momento.^[1]

Propriedades

Um semiprimo é sempre o quadrado de um número primo ou um número livre de quadrados.
O valor da função totiente de Euler para um número semiprimo n = pq é particularmente simples quando p e q são distintos:
φ(n) = (p − 1) (q − 1) = p q − (p + q) + 1 = n − (p + q) + 1.

Por outro lado, se p e q são o mesmo número,
φ(n) = φ(p²) = (p − 1) p = p² − p = n − p.
O número total de fatores primos de um semiprimo é por definição
$\Omega (pq)=2$
O conceito da função zeta primo pode ser adotado para semiprimos, definindo-se constantes como
$\sum _{\Omega (n)=2}{\frac {1}{n^{2}}}\approx 0.1407604$ (sequência A117543 na OEIS)

$\sum _{\Omega (n)=2}{\frac {1}{n(n-1)}}\approx 0.17105$ (sequência A152447 na OEIS)

$\sum _{\Omega (n)=2}{\frac {\ln n}{n^{2}}}\approx 0.28360$ (sequência A154928 na OEIS)

Aplicações

Os semiprimos são altamente úteis nas áreas de criptografia e de teoria dos números, mais especialmente na criptografia de chave pública onde são utilizados pelo RSA e pelos geradores de números pseudoaleatórios tais como o Blum Blum Shub. Estes métodos baseiam-se no facto de que encontrar dois números primos grandes e multiplicá-los é computacionalmente simples, enquanto encontrar os factores originais é bem mais difícil. Na competição de fatorização RSA, a RSA Security ofereceu prémios pela fatorização de grandes semiprimos específicos. O desafio mais recente terminou em 2007.^[2]

Na criptografia prática, não basta escolher qualquer semiprimo. Um bom número deve escapar de vários algoritmos de propósito especial bem conhecidos para a fatoração de números de certas formas. Os fatores p e q de n devem ser ambos bem grandes, e da mesma ordem de grandeza da raiz quadrada de n. Isso impraticável a divisão por tentativa e o algoritmo rho de Pollard. Ao mesmo tempo, eles não podem ser muito próximos um do outro, caso contrário o número poderá ser fatorado rapidamente pelo método de fatoração de Fermat. O número também pode ser escolhido de modo que um dos números p − 1, p + 1, q − 1, ou q + 1 seja liso, protegendo contra o algoritmo p − 1 de Pollard ou o algoritmo p + 1 de Williams. No entanto, estes testes não tem como levar em conta algoritmos futuros ou secretos, introduzindo-se a possibilidade de que os números em uso atualmente podem ser quebrados por algoritmos de propósito especial.

Em 1974 a mensagem de Arecibo foi enviada com um sinal de rádio que tinha como objetivo um aglomerado estelar. Consistiu em 1679 dígitos binários, previstos para serem interpretados como imagem bitmap. O número 1679 = 23×73 foi eleito porque é um semiprimo e portanto pode ser organizado apenas em 23 linhas e 73 colunas, ou 73 linhas e 23 colunas.

Ver também

Referências

↑ Chris Caldwell, «The Prime Glossary: semiprime» (em inglês). Consultado em 4 de dezembro de 2007
↑ «Cópia arquivada». Consultado em 14 de julho de 2008. Arquivado do original em 27 de julho de 2013

Ligações externas

«MathWorld: Semiprime» (em inglês)

v d e Classes de números primos
Por fórmula	Fermat $(2^{2^{n}}+1)$ Mersenne $(2^{p}-1)$ Duplo de Mersenne $(2^{2^{p}-1}-1)$ Wagstaff ${\frac {(2^{p}+1)}{3}}$ Proth $(k\cdot 2^{n}+1)$ Factorial $(n!\pm 1)$ Primorial $(p_{n}\#\pm 1)$ Euclides $(p_{n}\#+1)$ Pitagórico $(4n+1)$ Pierpont $(2^{u}\cdot 3^{v}+1)$ Solinas $(2^{a}\pm 2^{b}\pm 1)$ Cullen $(n\cdot 2^{n}+1)$ Woodall $(n\cdot 2^{n}-1)$ Cubano ${\frac {(x^{3}-y^{3})}{(x-y)}}$ Carol ${(2^{n}-1)}^{2}-2$ Kynea ${(2^{n}+1)}^{2}-2$ Leyland $(x^{y}+y^{x})$ Thabit $(3\cdot 2^{n}-1)$ Mills (chão $(A^{3^{n}})$ )
Por sequência de inteiros	Fibonacci Lucas Motzkin Bell Partições Pell Perrin Newman–Shanks–Williams
Por propriedade	Da sorte Wall–Sun–Sun Wilson Wieferich Par de Wieferich Afortunado Ramanujan Pillai Regular Forte Stern Supersingular Wolstenholme Bom Superprimo Higgs Altamente cototiente Ilegal
Dependentes de bases	Feliz Diédrico Palíndromo Omirp Repunit ${\frac {(10^{n}-1)}{9}}$ Permutável Circular Estrobogramático Mínimo Longo único Primeval Auto Smarandache–Wellin
Padrões	Gémeos $(p,p+2)$ Tripla $(p,p+2~ou~p+4,p+6)$ Quádrupla $(p,p+2,p+6,p+8)$ Tuplo Primos primos $(p,p+4)$ Sexy $(p,p+6)$ Chen Sophie Germain $(p,2p+1)$ Cadeia de Cunningham $(p,2p\pm 1,\ldots )$ Seguro $(p,{\frac {(p-1)}{2}})$ Progressão aritmética $(p+a\cdot n,n=0,1,\ldots )$ Equilibrado (consecutivos $p-n,p,p+n)$
Por dimensão	Titânico ( $1000+$ dígitos) Gigantesco ( $10000+$ ) Megaprimo ( $1000000+$ ) Maior conhecido
Números complexos	Eisenstein Gauss
Números compostos	Número pseudoprimo Quase primo Semiprimo Interprimo
Tópicos relacionados	Provável Nível industrial Fórmula para números primos Intervalo entre números primos consecutivos
Lista de números primos

Classes de números naturais

Potências e números relacionados

Aquiles
Potência de 2
Potência de 10
Quadrado
Cubo
Quarta potência
Quinta potência
Potência perfeita
Potente
Potência prima

Da forma a × 2^b ± 1

Outros números polinomiais

Carol
Hilbert
Idôneo
Kynea
Leyland
Números da sorte de Euler
Repunit

Números definidos recursivamente

Possuindo um conjunto específico
de outros números

Knödel
Riesel
Sierpiński

Expressáveis via somas específicas

Não-hipotenusa
Polido
Prático
Primário pseudoperfeito
Ulam
Wolstenholme

Gerado via uma teoria dos crivos

Sorte

Relacionado a codificação

Meertens

Números figurados

centrado	Triangular centrado Quadrado centrado Pentagonal centrado Hexagonal centrado Heptagonal centrado Octagonal centrado Nonagonal centrado Decagonal centrado Estrela
não-centrado	Triangular quadrado Quadrado triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

centrado	Tetraédrico centrado Cúbico centrado Octaédrico centrado Dodecaédrico centrado Icosaédrico centrado
Não-centrado	Tetraédrico Octaédrico Dodecaédrico Icosaédrico Stella octangula
Piramidal	Piramidal quadrado Piramidal pentagonal Piramidal hexagonal Piramidal heptagonal

centrado	Pentácoro centrado Triangular quadrado
Não-centrado	Pentácoro

Pseudoprimos

Número de Carmichael
Pseudoprimo de Catalan
Pseudoprimo elíptico
Pseudoprimo de Euler
Pseudoprimo de Euler–Jacobi
Pseudoprimo de Fermat
Pseudoprimo de Frobenius
Pseudoprimo de Lucas
Pseudoprimo de Somer–Lucas
Pseudoprimo forte

Números combinatoriais

Bell
Bolo
Catalan
Dedekind
Delannoy
Euler
Fuss–Catalan
Número poligonal central
Lobb
Motzkin
Narayana
Ordenado de Bell
Schröder
Schröder–Hipparchus

Funções aritméticas

Por propriedades de σ(n)	Abundante Quase perfeito Aritmético Colossalmente abundante Descartes Hemiperfeito Altamente abundante Altamente composto Hyperperfeito Multiplamente perfeito Perfeito Número prático Primitivo abundante Quase perfeito Refactorável Sublime Superabundante Superior altamente composto Superperfeito
Por propriedades de Ω(n)	Quasi-primo Semiprimo
Por propriedades de φ(n)	Altamente cototiente Altamente totiente Não-cototiente Não-totiente Perfeito totiente Esparsamente totiente
Por propriedades de s(n)	Amigo Quasi-amigo Defectivo Semiperfeito