Teste de primalidade

a Teste de primalidade é um algoritmo para determinar se um número de entrada é o Prime. Entre outros campos da matemática, é usado para criptografia. Diferentemente da fatoração inteira, os testes de primalidade geralmente não fornecem fatores primos, apenas afirmando se o número de entrada é primo ou não. Pensa -se que a fatorização é um problema computacionalmente difícil, enquanto o teste de primalidade é comparativamente fácil (seu tempo de execução é polinomial no tamanho da entrada). Alguns testes primitivos provam que um número é primo, enquanto outros como Miller - Rabin provam que um número é composto. Portanto, este último pode ser chamado de teste de composição em vez de testes de primalidade.

O teste de primalidade mais simples é divisão de julgamento: dado um número de entrada, $Não.$, verificar se é divisível por qualquer número primo entre 2 e $- Sim.$ (isto é, se a divisão não deixa nenhum resto). Se assim for, então $Não.$ é composto. Caso contrário, é primo. Para qualquer divisor ${\displaystyle p\geq {\sqrt {n}}}$Deve haver outro divisor ${\displaystyle n/p\leq {n}}}$e um grande divisor $Não.$ de $Não. Não.$, e, portanto, procurando divisores primos no máximo $- Sim.$ é suficiente.

Por exemplo, considere o número 100, cujos divisores são esses números:

1, 2, 4, 5, 10, 20, 25, 50, 100.

Quando todos os divisores possíveis até $Não.$ são testados, alguns divisores serão descobertos duas vezes.. Para observar isso, considere a lista de pares divisores de 100:

${\displaystyle 1\times 100,\;2\times 50,\;4\times 25,\;5\times 20,\;10\times 10,\;20\times 5,\;25\times 4,\;50\times 2,\;100\times 1$.

Produtos passados $10\times 10}$ são o reverso de produtos que apareceu anteriormente. Por exemplo, ${\displaystyle 5\times 20}$ e ${\displaystyle 20\times 5}$ são o reverso um do outro. Além disso, o dos dois divisores, ${\displaystyle 5\leq {\sqrt {100}}=10}$ e ${\displaystyle 20\geq {\sqrt {100}}=10}$. Esta observação generaliza-se a todos $Não.$: todos os pares divisor de $Não.$ conter um divisor inferior ou igual a $- Sim.$, então o algoritmo só precisa procurar divisores menos ou igual a $- Sim.$ para garantir a detecção de todos os pares divisor.

Além disso, 2 é uma primeira divisão 100, que imediatamente prova que 100 não é primo. Cada inteiro positivo exceto 1 é divisível por pelo menos um número primo pelo Teorema Fundamental da Aritmética. Portanto, o algoritmo só precisa procurar Primeiro divisores inferiores ou iguais $- Sim.$.

Por outro exemplo, considere como este algoritmo determina a primalidade de 17. Um tem ${\displaystyle 4<{\sqrt {17}}<5}$, e os únicos primos ${\displaystyle \leq {\sqrt {17}}}$ são 2 e 3. Nem divide 17, provando que 17 é primo. Por um último exemplo, considere 221. Um tem ${\displaystyle 14<{\sqrt {221}}<15}$e os primos ${\displaystyle \leq {\sqrt {221}}}$ são 2, 3, 5, 7, 11 e 13. Ao verificar cada um, descobre-se que $Não. 221/13=17$, provando que 221 não é primo.

Nos casos em que não é possível calcular a lista de primos ${\displaystyle \leq {\sqrt {n}}}$, também é possível simplesmente (e lentamente) verificar todos os números entre $Não. 2$ e $- Sim.$ para divisores. Uma otimização bastante simples é testar a divisibilidade por 2 e apenas os números ímpares entre 3 e $- Sim.$, uma vez que a divisibilidade por um número igual implica divisibilidade por 2.

Este método pode ser melhorado mais. Observe que todos os primos maiores que 3 são da forma $Não. 6k+i.$ para um inteiro nonnegative $Não.$ e ${\displaystyle i\in \{1,5\}}$. De fato, cada inteiro é da forma $Não. 6k+i.$ para um inteiro positivo $Não.$ e ${\displaystyle i\in \{0,1,2,3,4,5\}}$. Desde 2 divisões $- Sim.$e $- Sim.$, e 3 divisões $- Sim.$ e $- Sim.$, os únicos restos possíveis mod 6 para um primo maior que 3 são 1 e 5. Então, um teste de primalidade mais eficiente para $Não.$ é para testar se $Não.$ é divisível por 2 ou 3, então para verificar através de todos os números do formulário $- Sim.$ e $- Sim.$ que são ${\displaystyle \leq {\sqrt {n}}}$. Isso é quase três vezes mais rápido que testar todos os números até $- Sim.$.

Generalizando mais, todos os primos maiores do que $Não.$ (c primorial) são da forma ${\displaystyle c\#\cdot k+i}$ para $- Sim.$ inteiros positivos, ${\displaystyle 0\leq i$e $Não.$ coprime para $Não.$. Por exemplo, considere ${\displaystyle 6\#=2\cdot 3\cdot 5=30}$. Todos os inteiros são da forma $- Sim.$ para $- Sim.$ inteiros com ${\displaystyle 0\leq i<30}$. Agora, 2 divisões ${\displaystyle 0,2,4,\dots28}$, 3 divisões $Não.$, e 5 divisões ${\displaystyle 0,5,10,\dots25}$. Assim, todos os números primos maiores que 30 são da forma $- Sim.$ para ${\displaystyle i\in \{1,7,11,13,17,19,23,29\}}$. Claro, nem todos os números da forma ${\displaystyle c\#\cdot k+i}$ com $Não.$ coprime para $Não.$ são primos. Por exemplo, ${\displaystyle 19\cdot 23=437=210\cdot 2+17=2\cdot 7\#+17}$ não é primo, embora 17 é coprime para ${\displaystyle 7\#=2\cdot 3\cdot 5\cdot 7$.

Como $Não.$ cresce, a fração de restos de coprime a restos diminui, e assim o tempo para testar $Não.$ diminui (embora ainda seja necessário verificar a divisibilidade por todos os primos que são menos do que $Não.$). Observações análogas ao precedente podem ser aplicadas de forma recursiva, dando o Sieve de Eratosthenes.

Uma maneira de acelerar esses métodos (e todos os outros mencionados abaixo) é pré-computar e armazenar uma lista de todos os primos até um determinado limite, como todos os primos até 200. (Tal lista pode ser computada com o Sieve of Eratosthenes ou por um algoritmo que testa cada incremental $Não.$ contra todos os primos conhecidos ${\displaystyle \leq {m}}}$). Então, antes de testar $Não.$ para a primalidade com um método de grande escala, $Não.$ pode primeiro ser verificado para divisibilidade por qualquer primo da lista. Se é divisível por qualquer um desses números, então é composto, e quaisquer outros testes podem ser ignorados.

Um teste de primalidade simples, mas muito ineficiente, usa o teorema de Wilson, que afirma que $Não.$ é primo se e somente se:

$(p-1)!\equiv -1{\pmod {p}}}$

Embora este método requer $Não.$ multiplicações modulares, tornando-o impraticável, teoremas sobre primos e resíduos modulares formam a base de muitos métodos mais práticos.

Estes são testes que parecem funcionar bem na prática, mas não são comprovados e, portanto, não são, tecnicamente falando, algoritmos. O teste de Fermat e o teste de Fibonacci são exemplos simples, e eles são muito eficazes quando combinados. John Selfridge conjeturou que se p for um número ímpar e p ± 2 (mod 5), então p será o Prime se ambos do seguinte porão:

• 2^{p- Sim.} ≡ 1 (mod p),
• f_{p+ 1} ≡ 0 (mod p),

onde f k é o número k -th fibonacci. A primeira condição é o teste de primalidade de Fermat usando a base 2.

Em geral, se p ≡ a (mod x 2 +4), onde a é um não residência quadrática (mod x 2 +4) Então p deve ser primitiva se as seguintes condições mantiverem:

• 2^{p- Sim.} ≡ 1 (mod p),
• f(1)_{p+ 1} ≡ 0 (mod p),

f ( x ) k k -th fibonacci polinomial em x .

Selfridge, Carl Pomerância e Samuel Wagstaff juntos oferecem US $ 620 por um contra -exemplo.

Os testes probabilísticos são mais rigorosos do que as heurísticas, pois fornecem limites comprováveis sobre a probabilidade de serem enganados por um número composto. Muitos testes de primalidade popular são testes probabilísticos. Esses testes usam, além do número testado n , alguns outros números a que são escolhidos aleatoriamente em algum espaço de amostra; Os testes de primalidade randomizada usuais nunca relatam um número primo como composto, mas é possível que um número composto seja relatado como Prime. A probabilidade de erro pode ser reduzida repetindo o teste com vários valores escolhidos de forma independente de a ; Para dois testes comumente usados, para qualquer composto n pelo menos metade do a ' s composição, então as repetições k reduzem a probabilidade de erro para no máximo 2 - k , o que pode ser feito arbitrariamente pequeno, aumentando k k .

A estrutura básica dos testes de primalidade randomizada é a seguinte:

1. Escolha aleatoriamente um número um.
2. Verificar a igualdade (correspondente ao teste escolhido) envolvendo um e o número dado n. Se a igualdade não for verdadeira, então n é um número composto e um é um testemunha para a compósito, e o teste para.
3. Volte ao passo um até que a precisão necessária seja alcançada.

Após uma ou mais iterações, se n não for considerado um número composto, ele pode ser declarado provavelmente primitivo.

Teste de primalidade Fermat

O teste de primalidade probabilística mais simples é o teste de primalidade de Fermat (na verdade um teste de composição). Funciona da seguinte maneira:

Dado um inteiro n, escolher um inteiro um coprime para n e calcular um^{n - 1} Modulo n. Se o resultado for diferente de 1, então n é composto. Se for 1, então n pode ser primo.

se a n −1 (modulo n ) é 1, mas n não é primo, então n é chamado de pseudoprime para basear a . Na prática, se a n −1 (modulo n ) é 1, então n é geralmente primo. Mas aqui está um contra -exemplo: Se n = 341 e a = 2, então

${\displaystyle 2^{340}\equiv 1{\pmod {341}}}$

Embora 341 = 11 · 31 seja composto. De fato, 341 é a menor pseudoprime base 2 (ver Figura 1 de ).

Existem apenas 21853 Pseudoprimes Base 2 que são inferiores a 2,5 × 10 10 (consulte a página 1005 de). Isso significa que, para n até 2.5 × 10 10 , se 2 n −1 ( O módulo n ) é igual a 1, então n é primitivo, a menos que n seja um desses pseudoprimes 21853.

Alguns números compostos (números carmichael) têm a propriedade de que a n - 1 é 1 (modulo n ) Para cada a que é coprimônio para n . O menor exemplo é n = 561 = 3 · 11 · 17, para o qual a 560 é 1 (módulo 561) para todos A coprime a 561. No entanto, o teste de Fermat é frequentemente usado se for necessária uma triagem rápida de números, por exemplo, na fase de geração de chaves do algoritmo criptográfico de chave pública da RSA.

Miller–Rabin e Solovay–Strassen teste de primalidade

O teste de Primalidade Miller -Rabin e o teste de Primalidade Solovay -Sstrassen são variantes mais sofisticadas, que detectam todos os compósitos (mais uma vez, isso significa: para todo número composto n , pelo menos 3/4 (Miller -Rabin) ou 1/2 (Solovay -Sstrassen) de números a são testemunhas de composição de n ). Estes também são testes de composição.

O teste de primalidade de Miller -Rabin funciona da seguinte maneira: Dado um número inteiro n , escolha algum número inteiro positivo a & lt; n . Seja 2 s d = n - 1, onde d é estranho. Se

${\displaystyle a^{d}\not \equiv \pm 1{\pmod {n}}}$

e

${\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}$ para todos ${\displaystyle 0\leq r\leq s-1,}$

Então n é composto e a é uma testemunha da composição. Caso contrário, n pode ou não ser primo. O teste Miller -Rabin é um forte teste principal provável (consulte PSW página 1004).

O teste de Primalidade Solovay -Sstrassen usa outra igualdade: dado um número ímpar n , escolha algum número inteiro a & lt; n se

${\displaystyle a^{(n-1)/2}\not \equiv \left({\frac {a}{n}}\right){\pmod {n}}}$, onde ${\displaystyle \left({\frac {a}{n}}\right)}$ é o símbolo Jacobi,

Então n é composto e a é uma testemunha da composição. Caso contrário, n pode ou não ser primo. O teste Solovay -Sstrassen é um teste principal provável de Euler (consulte PSW página 1003).

Para cada valor individual de a , o teste Solovay -Sstrassen é mais fraco que o teste de Miller -Rabin. Por exemplo, se n = 1905 e a = 2, o teste de Miller-rabin mostra que n é composto, mas o Solovay-Sstrassen O teste não. Isso ocorre porque 1905 é um Euler Base 2 de pseudoprime, mas não uma base de pseudoprime forte 2 (isso é ilustrado na Figura 1 de PSW).

Teste de primalidade Frobenius

Os testes de Miller -Rabin e Solovay -Sstassen Primity são simples e são muito mais rápidos do que outros testes gerais de primalidade. Um método para melhorar ainda mais a eficiência em alguns casos é o teste de pseudoprimalidade de Frobenius; Uma rodada deste teste leva cerca de três vezes mais que uma rodada de Miller -Rabin, mas atinge uma probabilidade ligada a sete rodadas de Miller -Rabin.

O teste Frobenius é uma generalização do provável teste primo da Lucas.

Teste de primalidade de Baillie-PSW

O teste de primalidade Baillie-PSW é um teste de primalidade probabilístico que combina um teste de Fermat ou Miller-Rabin com um teste principal provável de Lucas para obter um teste de primalidade que não tem contraexemplos conhecidos. Isto é, não há composto conhecido n para o qual este teste relata que n provavelmente é primo. Foi demonstrado que não há contraexemplos para n ${\displaystyle <2^{64}}$.

Outros testes

Leonard Adleman e Ming-Deh Huang apresentaram uma variante sem erros (mas esperada em tempo polinomial) do teste de primalidade da curva elíptica. Diferentemente dos outros testes probabilísticos, esse algoritmo produz um certificado de primalidade e, portanto, pode ser usado para provar que um número é primo. O algoritmo é proibitivamente lento na prática.

Se os computadores quânticos estivessem disponíveis, a primalidade poderia ser testada assintoticamente mais rápido do que usando computadores clássicos. Uma combinação do algoritmo de Shor, um método de fatoração inteiro, com o teste de primalidade de Pocklington poderia resolver o problema em $(\log n)^{3}(\log \log n)^{2}\log \log \log n)}$.

Testes determinísticos rápidos

Perto do início do século XX, foi demonstrado que um corolário do pequeno teorema de Fermat poderia ser usado para testar a primalidade. Isso resultou no teste de primalidade de Pocklington. No entanto, como esse teste requer uma fatoração parcial de n - 1, o tempo de execução ainda era bastante lento no pior caso. O primeiro teste de primalidade determinística significativamente mais rápido que os métodos ingênuos foi o teste de ciclotomia; Seu tempo de execução pode ser comprovado como O ((log n ) c log log n ), onde < i> n é o número a testar para a primalidade e c é uma constante independente de n . Muitas melhorias adicionais foram feitas, mas nenhuma poderia ser comprovada ter um tempo de execução polinomial. (O tempo de execução é medido em termos do tamanho da entrada, que neste caso é ~ log n , sendo esse o número de bits necessário para representar o número n . ) O teste de primalidade da curva elípticos pode ser comprovada para executar em O ((log n ) 6 ), se algumas conjecturas sobre a teoria dos números analíticos forem verdadeiros. Da mesma forma, sob a hipótese generalizada de Riemann, o teste determinístico de Miller, que forma a base do teste probabilístico de Miller -Rabin, pode ser comprovado em (Log n ) ^{4 ). Na prática, esse algoritmo é mais lento que os outros dois para tamanhos de números que podem ser tratados. Como a implementação desses dois métodos é bastante difícil e cria um risco de erros de programação, os testes mais lentos, mas mais simples, são frequentemente preferidos.}

Em 2002, o primeiro teste de tempo polinomial determinístico comproperável compro condicional foi inventado por Manindra Agrawal, Neeraj Kayal e Nitin Saxena. O teste de primalidade do AKS é executado em õ ((log n ) 12 ) (melhorado para õ ((log n ) 7.5 ) na revisão publicada de seu artigo), que pode ser reduzida ainda mais a õ ((log n ) 6 ) se a conjectura de Sophie Germain for verdadeira. Posteriormente, Lenstra e Pomerância apresentaram uma versão do teste que é executada no tempo õ ((Log n ) 6 ) incondicionalmente.

Agrawal, Kayal e Saxena sugerem uma variante de seu algoritmo que seria executado em õ ((log n ) 3 se a conjectura agrawal é verdadeira; No entanto, um argumento heurístico de Hendrik Lenstra e Carl Pomerância sugere que provavelmente é falso. Uma versão modificada da conjectura de Agrawal, a conjectura Agrawal -Popovych, ainda pode ser verdadeira.

Complexidade

Na teoria da complexidade computacional, a linguagem formal correspondente aos números primos é indicada como primos. É fácil mostrar que os primos estão em co-np : seus compósitos de complemento estão em np porque se pode decidir composição ao adivinhar um fator não-determinante.

Em 1975, Vaughan Pratt mostrou que existia um certificado de primalidade que era conferível em tempo polinomial, e assim que PRIMES estava em NP, e, portanto, em ⁠${\displaystyle {\mathsf {NP\cap coNP}}}$⁠. Consulte o certificado de primalidade para obter detalhes.

A descoberta subseqüente dos algoritmos Solovay-Strassen e Miller-Rabin coloca o PRIMES no coRP. Em 1992, o algoritmo Adleman–Huang reduziu a complexidade para ⁠${\displaystyle {\mathsf {{\color} (Blue}ZPP}=RP\cap coRP}}}$⁠, que superou o resultado de Pratt.

O Adleman-Pomerância-Teste de Primalidade de 1983 colocou os primos em qp (tempo quase-polinomial), que não é conhecido por ser comparável às classes mencionadas acima.

Devido à sua tratabilidade na prática, algoritmos de tempo polinomial assumindo a hipótese de Riemann e outras evidências semelhantes, suspeitava-se há muito tempo, mas não comprovado que a primalidade poderia ser resolvida em tempo polinomial. A existência do teste de primalidade do AKS finalmente resolveu essa pergunta de longa data e colocou os primos em p . No entanto, os primos não são conhecidos por ser P-complete, e não se sabe se está em classes dentro de p como NC ou L. Sabe-se que os primos não estão no AC0.

Métodos teóricos de números

Existem certos métodos teóricos de números para testar se um número é primo, como o teste de Lucas e o teste de Proth. Esses testes normalmente requerem fatoração de n + 1, n -1 ou uma quantidade semelhante, o que significa que eles não são úteis para testes primitivos de uso geral, mas são Muitas vezes, é muito poderoso quando o número testado n é conhecido por ter uma forma especial.

O teste de Lucas depende do fato de que a ordem multiplicativa de um número a módulo n é n - 1 para um primo n quando a é um módulo de raiz primitivo n. Se pudermos mostrar a é primitivo para n , podemos mostrar que n é o Prime.

Referências

1. ↑ a b Riesel (1994) pp.2-3
2. ^ Conjectura de John Selfridge#Selfridge sobre testes de primalidade.
3. ↑ a b d e Pomerance, Carl; Selfridge, John L.; Wagstaff, Samuel S. Jr. (julho de 1980). "Os pseudoprimes a 25·109" (PDF). Matemática da Computação. 35 (151): 1003–1026. - Sim.10.1090/S0025-5718-1980-0572872-7.
4. ^ Baillie, Robert; Wagstaff, Samuel S. Jr. (outubro de 1980). Lucas Pseudoprimes (PDF). Matemática da Computação. 35 (152): 1391–1417. - Sim.10.1090/S0025-5718-1980-0583518-6MR 0583518.
5. ^ Baillie, Robert; Fiori, Andrew; Wagstaff, Samuel S. Jr. (julho de 2021). «Strengthening the Baillie-PSW Primality Test» (em inglês). Matemática da Computação. 90 (330): 1931-1955. - Sim.2006.14425. doi:10.1090/mcom/3616. S2CID 220055722.
6. ↑ a b Adleman, Leonard M.; Huang, Ming-Deh (1992). Teste de primalidade e variedades Abelianas em campo finito. Notas de palestra em matemática. Vol. 1512. Springer-Verlag. ISBN 3-540-55308-8.
7. ^ Chau, H. F.; Lo, H.-K. (1995). «Primality Test Via Quantum Factorization» (em inglês). - Sim.quant-ph/9508005.
8. ^ Pocklington, H. C. (1914). «A determinação da natureza primo ou composta de grandes números por teorema de Fermat». Cambr, Phil. Proc.. 18.: 29–30. JFM 45.1250.02.
9. ^ Weisstein, Eric W. «Pocklington's Theorem» (em inglês). Matemática.
10. ^ Gary L. Miller (1976). «Riemann's Hypothesis and Tests for Primality» (em inglês). Journal of Computer and System Sciences. 13 (3): 300–317.10.1016/S0022-0000(76)80043-8.
11. ↑ a b Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "Primes está em P" (PDF). Anais de Matemática. 160 (2): 781–793. doi:10.4007/annals.2004.160.781.
12. ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está em P" (PDF). Anais de Matemática. 160 (2): 781–793. doi:10.4007/annals.2004.160.781.
13. ^ Carl Pomerance & Hendrik W. Lenstra (20 de julho de 2005). "Testemunalidade com períodos gaussianos" (PDF).
14. ^ Popovych, Roman (30 de dezembro de 2008). Uma nota sobre conjectura de Agrawal (PDF).
15. ^ Allender, Eric; Saks, Michael; Shparlinski, Igor (2001). «A Lower Bound for Primality» (em inglês). Journal of Computer and System Sciences. 62 (2): 356–366. doi:10.1006/jcss.2000.1725.

Fontes

• Crandall, Richard; Pomerance, Carl (2005). Números Prime: Uma Perspectiva Computacional (2a ed.). Springer. ISBN 0-387-25282-7. Capítulo 3: Reconhecendo os Primes e Compostos, pp. 109–158. Capítulo 4: Prova de Primalidade, pp. 159–190. Seção 7.6: Prova de primalidade de curva elíptica (ECPP), pp. 334–340.
• Knuth, Donald (1997). «section 4.5.4» (em inglês). A arte da programação de computadorVol. 2: Algoritmos seminuméricos (3a ed.). Addison–Wesley. pp. 391–396. ISBN 0-201-89684-2.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). «Section 31.8: Primality testing» (em inglês). Introdução aos Algoritmos (Segunda edição). MIT Press, McGraw–Hill. pp. 887–896. ISBN 0-262-03293-7.
• Papadimitriou, Christos H. (1993). «Seção 10.2: Primality» (em inglês). Complexidade Computacional (1a ed.). Addison Wesley. pp. 222–227. ISBN 0-201-53082-1. Zbl 0833.68049.
• Riesel, Hans (1994). Números Prime e Métodos de Computador para a Factorização. Progresso em Matemática. Vol. 126 (segundo ed.). Boston, Massachusetts: Birkhäuser. ISBN 0-8176-3743-5. Zbl 0821.11001.

Ligações externas

• Solovay-Strassen (computacion.cs.cinvestav.mx) no archive.today (archived 2012-12-20) – Implementação do teste de primalidade Solovay-Strassen no Maple
• Distinguindo números primos de números compostos, por D.J. Bernstein (cr.yp.to)
• As primeiras páginas (primes.utm.edu)
• Lucas Primality Teste com Factored N − 1 (MathPages.com) na Biblioteca do Congresso Web Archives (archived 2010-08-06)
• PRIMABOINCA é um projeto de pesquisa que usa computadores conectados à Internet para procurar um contra-exemplo para algumas conjecturas. A primeira conjectura (conjectura de Agrawal) foi a base para a formulação do primeiro algoritmo de teste principal determinístico em tempo polinomial ( algoritmo deAKS).