A primeira etapa do algoritmo de teste de primalidade AKS é verificar se o número de entrada é uma potência perfeita. Parece que esse é um fato bem conhecido na teoria dos números, uma vez que o artigo não a explicou em detalhes. Alguém pode me dizer como fazer isso em tempo polinomial? Obrigado.
23
Respostas:
Dado um número n, se é que pode ser escrito como (b> 1), então . E para cada fixo , é possível verificar se existe um com usando pesquisa binária. O tempo total de execução é, portanto, eu acho. b < log ( n ) + 1 b a a b = n O ( log 2 n )ab b<log(n)+1 b a ab=n O(log2n)
fonte
Veja Bach e Sorenson, algoritmos de peneira para teste de potência perfeita, Algorithmica 9 (1993), 313-328, DOI: 10.1007 / BF01228507, e DJ Bernstein, Detectando potências perfeitas em tempo essencialmente linear, Math. Comp. 67 (1998), 1253-1283.
fonte
Encontrei uma solução interessante e elegante no artigo: Sobre a implementação do teste de primalidade da classe AKS, por R.Crandall e J.Padadopoulos, 18 de março de 2003.
fonte
De alguma forma, posso mostrar que o algoritmo de busca binária é .O(lg n⋅(lg lg n)2)
Primeiramente, , existe b < l g n . Algoritmo de pesquisa binária: Para cada b , usamos a pesquisa binária para encontrar a .ab=n b<lg n
b a
Cada vez que o cálculo de custa l g b = l g l g n operações usando exponenciação rápida . Portanto, o problema restante é o intervalo de a .ab lg b=lg lg n a
Se é o valor máximo possível de a , a pesquisa binária precisa de operações l g AA a lg A
Observe que , ou seja, l g A = l g nb lg a=lg n
Ao resumir,
∑lgA=lgn⋅(1
Em outras palavras, todas as operações para pesquisa binária sãoO(lg n⋅lg lg n)
ps: Todos os lg são base 2.
Código Python:
fonte