Decidindo se um intervalo contém um número primo

14

Qual é a complexidade de decidir se um intervalo dos números naturais contém um primo? Uma variante da Peneira de Eratóstenes fornece um algoritmo , onde é a duração do intervalo e oculta fatores polialogarítmicos no ponto inicial do intervalo; podemos fazer melhor (apenas em termos de )?O~(L)LL

Elliot Gorokhovsky
fonte
1
Nitpick: The Sieve of Eratóstenes não fornece apenas fatores polilogarítmicos no ponto de partida, mesmo para um intervalo de comprimento 1. É realmente possível verificar se um número é primo, se o tempo é polilogarítmico no número (= polinômio no tamanho da representação), mas isso requer um algoritmo muito mais sofisticado do que a peneira de Eratóstenes.
Vanessa
1
@Squark True, deveria ter especificado "pseudoprime em relação a uma base de fatores especificada". Embora como o ponto do intervalo começando se torna grande, o custo esperado de teste de primalidade vai a zero ...
Elliot Gorokhovsky

Respostas:

27

Disclaimer : Eu não sou um especialista em teoria dos números.

Resposta curta : se você estiver disposto a assumir "conjecturas teóricas razoáveis", podemos dizer se existe um primo no intervalo no tempo p o l y l o g ( n ) . Se você não está disposto a fazer tal suposição, então há uma bela algoritmo devido a Odlyzko que atinge n 1 / 2 + o ( 1 ) , e eu acredito que este é o mais conhecido.[n,n+Δ]polylog(n)n1/2+o(1)

Link muito útil com muitas informações excelentes sobre um problema intimamente relacionado : Projeto PolyMath sobre algoritmos determinísticos para localização de números primos .

Resposta longa :

Esse é um problema difícil, uma área ativa de pesquisa, e parece estar intimamente ligado à difícil questão de estabelecer lacunas entre os primos. Seu problema é moralmente muito semelhante ao de encontrar um primo entre e 2 n deterministicamente, que foi recentemente o assunto de um projeto PolyMath . (Se você realmente quiser se aprofundar nessas questões, esse link é um ótimo ponto de partida.) Em particular, nossos melhores algoritmos para os dois problemas são essencialmente os mesmos.n2n

Nos dois casos, o melhor algoritmo depende muito do tamanho das lacunas entre os primos. Em particular, se é tal que sempre existe um primo entre n e n + f ( n ) ( ef ( n ) pode ser computado com eficiência), então sempre podemos encontrar um primo no tempo p o l y l O g ( n ) f ( n ) como se segue. Para determinar se existe um primo entre n e n +f(n)nn+f(n)f(n)polylog(n)f(n)n , verifique primeiro se Δ f ( n ) . Se sim, emita sim. Caso contrário, basta percorrer os números inteiros entre n e n + Δ e testar cada um quanto à primalidade e responder sim se você encontrar um primo e não o contrário. (Isso pode ser feito deterministicamente, e é por isso que encontrar determinamente um primo entre n e 2 n está tão intimamente relacionado à determinação de se existe um primo em um determinado intervalo.)n+ΔΔf(n)nn+Δn2n

Se os números primos se comportar como nós pensamos que eles fazem, então este é o fim da história (até fatores). Em particular, esperamos poder tomar f ( n ) = O ( log 2 n ) . Isso é conhecido como conjectura de Cramér depois de Harald Cramér, e provando que parece muito distante do alcance no momento. Mas, tanto quanto eu sei, é amplamente aceito. (Chega-se a essa conjectura, por exemplo, a partir da heurística de que os primos se comportam como o conjunto aleatório de números inteiros obtido pela inclusão de cada número inteiro n 3polylog(n)f(n)=O(log2n)n3independentemente aleatoriamente com probabilidade .)1/logn

Existem muitas conjecturas que implicam o limite muito mais fraco , comoa conjectura de Legendre. (Não conheço nenhuma conjectura que implique um limite intermediário, embora eu imagine que exista.) E, sabe-se que a hipótese de Riemann implica o limite similarf(n)O(f(n)O(n). Portanto, se você assume essas conjecturas, combina essencialmente o algoritmo de Odlyzko (um fator den o ( 1 ) ) com um algoritmo muito mais simples.f(n)O(nlogn)no(1)

Acredito que o melhor limite incondicional no momento é devido a Baker, Harman e Pintz . Portanto, se você não assume nada, o algoritmo de Odlyzko vence o óbvio por aproximadamente um fator de n 0,025 .O~(n0.525)n0.025

Noah Stephens-Davidowitz
fonte
3
Esta resposta é incrível! Essas abordagens podem ser adaptadas para decidir se existem primos no intervalo em que k é um número determinado? E qual é a complexidade nesse caso? kk
Michael Wehar
3
@MichaelWehar Nice question. O algoritmo de Odlyzko definitivamente pode, pois seu algoritmo realmente calcula a função de contagem principal . Para a abordagem que usa lacunas entre os números primos, eu não sou o cara certo para perguntar. Obviamente, isso requer limites em p n + k - p n , em vez de apenas p n + 1 - p n , e eu simplesmente não sei muito sobre isso. Talvez alguém mais saiba? π(x):=\# primes below xpn+kpnpn+1pn
Noah Stephens-Davidowitz