Comment vérifier si un nombre est une puissance parfaite en temps polynomial

23

La première étape de l'algorithme de test de primalité AKS consiste à vérifier si le numéro d'entrée est une puissance parfaite. Il semble que ce soit un fait bien connu de la théorie des nombres, car l'article ne l'explique pas en détail. Quelqu'un peut-il me dire comment faire cela en temps polynomial? Merci.

yzll
la source
7
La première étape de l'algorithme AKS consiste à tester si le nombre d'entrée est une puissance parfaite (un nombre de la forme pour certains entiers c, n> 1), ce qui est différent de tester si le nombre est une puissance première. Le test pour une puissance parfaite est l'exercice 9.44 du livre cité dans l'article ( Modern Computer Algebra de von zur Gathen et Gerhard, 2003). Je n'ai pas lu le livre et je ne connais pas la réponse, mais vous avez consulté le livre? cn
Tsuyoshi Ito du
1
Je crois que la première étape de l'AKS vérifie si le nombre est une puissance d'un entier positif, pas nécessairement un nombre premier. Si on avait su vérifier une puissance première en temps polynomial avant AKS, cela aurait déjà donné un testeur de primalité de temps polynomial.
arnab
@Tsuyoshi Merci d'avoir signalé mon erreur. Je n'ai pas consulté le livre.
yzll
2
Si vous vous souciez de la question , essayez de résoudre le problème avant de la poster.
Tsuyoshi Ito
Tsuyoshi / arnab, peut-être devriez-vous republier comme réponses afin que cela puisse être accepté?
Suresh Venkat

Réponses:

31

Étant donné un nombre n, s'il peut être écrit sous la (b> 1), alors b < log ( n ) + 1 . Et pour chaque b fixe , vérifier s'il existe un a avec un b = n peut être fait en utilisant la recherche binaire. La durée totale de fonctionnement est donc O ( log 2 n ) je suppose.unebb<bûche(n)+1buneuneb=nO(bûche2n)

Ramprasad
la source
5
La réponse de Ramprasad laisse de côté le temps de faire l'exponentiation qui est . Une autre façon est de choisir b puis de calculer la b ème racine de n qui aurait un temps total de O ( l o g 3 n ) . O(log3n)bbnO(log3n)
David Marquis
1
Une amélioration simple qui supprime davantage un facteur en choisissant uniquement b . bûchebûchenb
Chao Xu
16

Voir Bach et Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), 313-328, DOI: 10.1007 / BF01228507, et DJ Bernstein, Detecting perfect pouvoirs in essentiellement linear time, Math. Comp. 67 (1998), 1253 à 1283.

Jeffrey Shallit
la source
Il existe également un document de suivi avec un temps de fonctionnement asymptotique amélioré et un traitement plus simple: DJ Bernstein, HW Lenstra Jr. et J. Pila, Détecter les pouvoirs parfaits en intégrant les coprimes, Math. Comp. 76 (2007), 385–388.
Erick Wong du
3

J'ai trouvé une solution intéressante et élégante dans l'article: sur la mise en œuvre du test de primalité de classe AKS, par R.Crandall et J.Papadopoulos, 18 mars 2003.

Plomb
la source
2

D'une certaine manière, je peux montrer que l'algorithme de recherche binaire est .O(lg n(lg lg n)2)

Tout d'abord, , il y a b < l g n . Algorithme de recherche binaire: Pour chaque b , nous utilisons la recherche binaire pour trouver a .uneb=nb<lg n
bune

Chaque fois, le calcul d' coûte l g b = l g l g n opérations en utilisant une exponentiation rapide . Par conséquent, le problème restant est la plage de a .uneblg b=lg lg nune

Si est la valeur maximale possible de a , alors la recherche binaire a besoin de l g opérations AUNEunelg UNE

Notez que , soit l g A = l g nb lg une=lg n résumer, lgA=lgn(1

lg UNE=lg nb
lg UNE=lg n(11+12+...+1B)=lg nlg B=lg nlg lg n

O(lg nlg lg n)

unebO(lg n(lg lg n)2)

ps: Tous les lg sont en base 2.

Code Python:

#--- a^n ---------------------------------------
def fast_exponentation(a, n):
    ans = 1
    while n:
        if n & 1 : ans = ans * a
        a = a * a
        n >>= 1
    return ans
#------------------------------------------
# Determines whether n is a power a ^ b, O(lg n (lg lg n) ^ 2)
def is_power(n):
    if (- n & n) == n: return True  # 2 ^ k
    lgn = 1 + ( len( bin ( abs ( n ) ) ) - 2)
    for b in range(2,lgn):
        # b lg a = lg n
        lowa = 1L
        higha = 1L << (lgn / b + 1)
        while lowa < higha - 1:
            mida = (lowa + higha) >> 1
            ab = fast_exponentation(mida,b) 
            if ab > n:   higha = mida
            elif ab < n: lowa  = mida
            else:   return True # mida ^ b
    return False
Kevin
la source