Teste de Primalidade - Tópicos Scaler (2023)

Visão geral

Oteste de primalidadeé um algoritmo para determinar se um determinado inteiro positivo é um número primo ou não. Existem muitos métodos para verificar se um número é primo ou não, como,o método escolar,Método de Divisão de Julgamento,Teste de primalidade de Fermat, eTeste de primalidade de Miller-Rabin.

Âmbito do artigo

• Neste artigo vamos discutir diferentestestes de primalidadeemestruturas de dados.
• Todostestes de primalidadesão explicados usando etapas e pseudocódigo neste artigo.
• A análise da complexidade de cada método também será discutida neste artigo.
• Os programas são executados emC++,Java, ePitãoneste artigo.

Algoritmo para determinar se um dado inteiro positivo é um número primo ou não:

• método escolar
• Método de Divisão de Julgamento
• Teste de primalidade de Fermat
• Teste de Primalidade de Miller-Rabin

O que é Teste de Primalidade?

Oteste de primalidadeé um algoritmo para determinar se um dado inteiro positivo é um número primo ou não.

A primalidade de um número também pode ser verificada determinando se é um número composto ou não, porque se o número não for umnúmero compostonem1, então deve ser um número primo.

Exemplo

Código Fonte - C++17

Código Fonte - Java (1.8)

Código fonte - Python 3

A saída é a mesma para todas as implementações, pois elas executam a mesma coisa, sendo a única diferença a linguagem de programação.

Saída

Nos exemplos acima, estamos verificando se o número dado é um número primo ou não, para isso, estamos iterando de$2$2para$n-1$n−1para verificar se esses números dividem o número dado. Se o fizerem, então o número dado não é um número primo, caso contrário, é um número primo.

método escolar

Ométodo escolaré uma solução simples que vem primeiro à mente de todos para verificação de primalidade, pois é a mais simples de todas.

NoMétodo Escolaralgoritmo, iteramos todos os números de$2$2para$n-1$n−1(o número a ser verificado é$n$n) e verifique se eles dividem o número$n$n.

Análise de Complexidade

Complexidade de tempo:$SOBRE)$O(N)

Ocomplexidade de tempoda verificação de primalidade do Método Escolar é$SOBRE)$O(N)enquanto iteramos$N-2$N−2vezes.

Complexidade Espacial:$O(1)$O(1)

Ocomplexidade do espaçoaqui é constante.

O algoritmo no exemplo acima é apenas School Method.

Método Escolar Otimizado

NoMétodo Escolar, podemos fazer algumas otimizações como:

• Em vez de verificar até$n$n, vamos verificar até$\sqrt{n}$n​porque um fator de$n$nmaior que$\sqrt{n}$n​deve ser um múltiplo de um número menor que$\sqrt{n}$n​que já foi verificado e não deve ser verificado novamente.
• Vamos primeiro verificar a divisibilidade de$n$npor$2$2e$3$3, então verifique sua divisibilidade por números da forma$6k-1$6k−1e$6k+1$6k+1Começando às$k=1$k=1. Fazemos isso porque qualquer inteiro maior que$4$4pode ser expresso na forma de$6k-1$6k−1,$6k$6k,$6k+1$6k+1,$6k+2$6k+2,$6k+3$6k+3, e$6k+4$6k+4(para$k>0$k>0), mas inteiros da forma$6k$6k,$6k+2$6k+2,$6k+3$6k+3, e$6k+4$6k+4será divisível por$2$2ou$3$3.

Vamos dar uma olhada em sua implementação na seção abaixo.

Implementação do Método Escolar Otimizado

Código Fonte - C++17

Código Fonte - Java (1.8)

Código fonte - Python 3

A saída é a mesma para todas as implementações, pois elas executam a mesma coisa, sendo a única diferença a linguagem de programação.

Saída

Nos exemplos acima, estamos verificando se o número dado é um número primo ou não, para isso, primeiro verificamos sua divisibilidade por$2$2e$3$3, verificando então sua divisibilidade por números da forma$6k-1$6k−1e$6k+1$6k+1. Se o número dado for divisível por qualquer número, então não é um número primo, senão é.

Análise de Complexidade

Complexidade de tempo:$O(\sqrt{N})$O(N​)

O assintóticocomplexidade de tempoda verificação de primalidade do Método Escolar Otimizado é$O(\sqrt{N})$O(N​)porque nós iteramos$\sqrt{N}/6$N​/6($i+=6$eu+=6no loop for) vezes neste algoritmo.

Complexidade Espacial:$O(1)$O(1)

Ocomplexidade do espaçoaqui é constante.

Método de Divisão de Julgamento

OMétodo de Divisão de Julgamentoé um algoritmo de verificação de primalidade no qual aceitamos algum inteiro$n$n, verifique se algum número de2para$\sqrt{n}$n​divide o inteiro dado, se um divisor for encontrado, então$n$né um número composto, caso contrário, é um número primo. É muito semelhante ao método escolar.

Análise de Complexidade

Complexidade de tempo:$O(\sqrt{N})$O(N​)

Ocomplexidade de tempoda verificação de primalidade do The Trial Division é$O(\sqrt{N})$O(N​)enquanto iteramos$\sqrt{N}-1$N​−1vezes.

Complexidade Espacial:$O(1)$O(1)

Ocomplexidade do espaçoaqui é constante.

Teste de primalidade de Fermat

OPrimalidade de FermatO teste é um método probabilístico para determinar se o inteiro dado é um número primo provável ou não.

É baseado emPequeno Teorema de Fermatque afirma se$p$pé um número primo e$a$anão é divisível por$p$p, então$a^{p-1} \equiv 1\;(mod\;p)$ap−1≡1(modp), ou seja$a^{p-1} = k*p + 1$ap−1=k∗p+1(onde$k$ké uma constante inteira).

Se quisermos testar$p$ppara um número primo, então vamos pegar alguns números inteiros aleatórios$a$aque não são divisíveis por$p$pe veja se a congruência se mantém ou não. Se a congruência não for válida para um valor de$a$a, então será uma prova de que$p$pé um número composto, mas se a congruência for válida para mais de um valor de$a$a, então$p$pé um provável número primo.

Passos do Algoritmo

• Repita o seguinte$k$kvezes (maior valor de$k$kindica maior probabilidade de resultados corretos):
  • Lidar com casos de canto para$p<3$p<3($p$pé o número a ser testado).
  • Escolha um número aleatório$a$ano intervalo$1 < a < p$1<a<p.
  • Se$a^{p-1} \not\equiv 1\;(mod\;p)$ap−1̸≡1(modp), então retorne$Falso$Faeuse.
• Retornar$Verdadeiro$Trvocêe,$p$pé provavelmente um número primo.

Exemplo

Vamos supor, temos que verificar se$n = 221$n=221é um número primo ou não. Vamos escolher aleatoriamente um número$a$ano intervalo$1 < um < 221$1<a<221. Em seguida, verificaremos se a congruência é válida ou não.

Para$a = 38$a=38,

$38^{221-1} \equiv 1\;(mod\;221)$38221−1≡1(mod221), como$a^{p-1} \equiv 1\;(mod\;p)$ap−1≡1(modp)$=> 38^{220} \equiv 1\;(mod\;221)$=>38220≡1(mod221),

Agora pode haver dois casos,$221$221é um número primo, ou$38$38é um mentiroso Fermat. Para prosseguir, vamos pegar$a=24$a=24.

mas,$24^{220} \not\equiv 1\;(mod\;221)$24220̸≡1(mod221), como$24^{220} \equiv 81\;(mod\;221)$24220≡81(mod221).

Isso prova que$221$221é um número composto e$38$38é Fermat mentiroso,$24$24sendo a testemunha de Fermat para a composição de$221$221.

Análise de Complexidade

Complexidade de tempo:$O(K*log(N))$O(k∗euog(N))

Aqui,$k$ké o número de iterações e$N$Né o número a ser testado quanto à primalidade.$registro(N)$euog(N)é a complexidade de tempo para computação$a^{p-1}$ap−1e o algoritmo é repetido$k$kvezes. Então a complexidade de tempo é$O(K*log(N))$O(k∗euog(N)).

Complexidade Espacial:$O(1)$O(1)

Não há necessidade de espaço extra, portanto a complexidade do espaço é constante.

O pequeno teorema de Fermat é usado para mais um teste de Primalidade, chamado de Teste de Primalidade de Miller-Rabin.

Teste de Primalidade de Miller-Rabin

OTeste de Primalidade de Miller-Rabintambém é um método probabilístico para determinar se o inteiro dado é um número primo ou não, semelhante ao Teste de Primalidade de Fermat. Também é baseado no Pequeno Teorema de Fermat (discutido na seção acima).

Este teste foi descoberto por Gary Lee Miller em1976, posteriormente modificado por Michael Oser Rabin em1980.

O resultado deste teste será se o número dado é um número composto ou um provável número primo. Os prováveis ​​números primos noTeste de Primalidade de Miller-Rabinsão chamados de números prováveis ​​fortes, pois têm uma chance maior de ser um número primo do que noTeste de Primalidade de Fermat.

Um número$n$né dito ser um número primo provável forte para basear$a$ase uma dessas relações de congruência (relações de equivalência na aritmética de módulo,$A \equiv B(mod\;C)$A≡B(modC)significa$A$Aé congruente com$B$Bmódulo$C$C) detém:

• $a^d \equiv 1\;(mod\;n)$ad≡1(modn)
• $a^{2^{r}*d} \equiv -1\;(mod\;n)$a2r∗d≡−1(modn)

Passos do Algoritmo

$n$né o número a ser testado.

$k$kindica a precisão do teste.

$d$dé um número ímpar tal que$n-1$n−1pode ser escrito na forma de$d*2^r$d∗2r(Desde$n$né estranho,$n-1$n−1deve ser par e$r>0$r>0).

$isPrime(int\; n, int\; k)$eusPreume(euntn,euntk)

• Lidar com casos base para$n <3$n<3.
• se$n$né par, retorne$Falso$Faeuse.
• Encontrar um número ímpar$d$d.
• Faça o seguinte$k$kvezes:
  • Verifique se$millerTest(n, d)==false$meueueuerTest(n,d)==faeuse, se sim, retorne$Falso$Faeuse.
• Retornar$Verdadeiro$Trvocêe.

$millerRabinTest(int \;n, int \;d)$meueueuerRabeunTest(euntn,euntd)

• Escolha um número aleatório$a$ano intervalo$2 \leq a \leq n-2$2≤a≤n−2.
• CalcularErro de análise do KaTeX: Esperado 'EOF', obtido '%' na posição 15: x = pow(a, d) %̲ n.
• Retornar$Verdadeiro$Trvocêese$x==1 \;ou \;x==n-1$x==1orx==n−1.
• Faça o loop a seguir até$d == n-1$d==n−1.
  • $x = (x*x)\%n$x=(x∗x)%n.
  • Retornar$Falso$Faeusese$x==1$x==1.
  • Retornar$Verdadeiro$Trvocêese$x==n-1$x==n−1.

Implementação daTeste de Primalidade de Miller-Rabin

Código Fonte - C++17

Código Fonte - Java (1.8)

Código fonte - Python 3

A saída é a mesma para todas as implementações, pois elas executam a mesma coisa, sendo a única diferença a linguagem de programação.

Saída

Nos exemplos acima, estamos verificando se o número dado é um provável número primo ou um número composto, para isso, estamos utilizando o Teste de Primalidade de Miller-Rabin. Se a função retornar$Verdadeiro$Trvocêe, então o número dado é um provável número primo, caso contrário, é um número composto.

O Teste de Miller-Rabin, sendo uma extensão do Teste de Primalidade de Fermat, é mais preciso do que o Teste de Primalidade de Fermat, portanto, é preferível a ele.

Análise de Complexidade

Complexidade de tempo:$O(K*log^3(N)$O(k∗euog3(N)

Ocomplexidade de tempodo teste de primalidade de Miller-Rabin é$O(K*log^3(N)$O(k∗euog3(N), onde$N$Né o número a ser verificado quanto à primalidade e$k$ké o número de iterações executadas para precisão de acordo com o requisito.

Complexidade Espacial:$O(1)$O(1)

Não há necessidade de espaço extra, portanto a complexidade do espaço é constante.

Conclusão

• testes de primalidadesão usados ​​para determinar se um determinado número é primo ou não.
• O método School é um algoritmo ingênuo de$SOBRE)$O(N)complexidade do tempo.
• O método Optimized School e o algoritmo Trial Division têm uma complexidade de tempo de$O(\sqrt{n})$O(n​).
• OTeste de primalidade de Fermate o teste de primalidade de Miller-Rabin retornam se um número é composto ou um primo provável e são baseados no Pequeno Teorema de Fermat.
• A complexidade temporal doTeorema da Primalidade de Fermaté$O(K*log(N))$O(k∗euog(N)).
• A complexidade temporal doTeste de Primalidade de Miller-Rabiné$O(K*log^3(N)$O(k∗euog3(N).