cómo determinar rápidamente si un número natural es un poder de cualquier otro número natural?

Question

Tenemos un número natural $n>1$. Queremos determinar si existe alguna números naturales $a, k>1$ tal que $n = a^k$.

Por favor, sugiera un polinomio en tiempo del algoritmo.

Answer 1

Esto se puede hacer en "esencialmente lineal del tiempo." Echa un vistazo Daniel Bernstein página web: http://cr.yp.to/arith.html

Especialmente nota de sus artículos con la etiqueta [poderes] y [powers2].

Answer 2

El sistema de álgebra computacional BRECHA realiza esta prueba y determina un más pequeño raíz de $a$ de un entero dado $n$ muy eficiente. El siguiente es copiar directamente desde su código fuente (archivo gap4r6/lib/entero.gi), y se explica por sí mismo:

#############################################################################
##
#F  SmallestRootInt( <n> )  . . . . . . . . . . . smallest root of an integer
##
InstallGlobalFunction(SmallestRootInt,

  function ( n )

    local   k, r, s, p, l, q;

    # check the argument
    if   n > 0  then k := 2;  s :=  1;
    elif n < 0  then k := 3;  s := -1;  n := -n;
    else return 0;
    fi;

    # exclude small divisors, and thereby large exponents
    if n mod 2 = 0  then
        p := 2;
    else
        p := 3;  while p < 100  and n mod p <> 0  do p := p+2;  od;
    fi;
    l := LogInt( n, p );

    # loop over the possible prime divisors of exponents
    # use Euler's criterion to cast out impossible ones
    while k <= l  do
        q := 2*k+1;  while not IsPrimeInt(q)  do q := q+2*k;  od;
        if PowerModInt( n, (q-1)/k, q ) <= 1  then
            r := RootInt( n, k );
            if r ^ k = n  then
                n := r;
                l := QuoInt( l, k );
            else
                k := NextPrimeInt( k );
            fi;
        else
            k := NextPrimeInt( k );
        fi;
    od;

    return s * n;
end);

Answer 3

Para cada una de las $k \le \log n/\log 2$, calcular una aproximación a la real positivo $k$-ésima raíz de $n$ utilizando el método de Newton a la precisión suficiente para comprobar si es un entero. Como alternativa, el uso de $p$-ádico raíces para un adecuado $p$, con Newton convirtiendo en Hensel.

Answer 4

Con el fin de probar si es o no un número natural $n$ es un poder perfecto, nos puede llevar a cabo una binario la búsqueda de los números enteros {1,2,...,n} para un número un número $m$ tal que $n = m^b$ algunos $b>1$. Deje $b>1$. Si una solución de $m$ $m^b =n$existe,entonces debía de estar en algún intervalo $[c_i,d_i]$. Al $i = 0$ podemos tomar $[c_0,d_0] = [1,n]$. A definir $[c_{i+1},d_{i+1}]$, considere la posibilidad de $\alpha:= \left\lfloor \frac{(ci+di)}{2}\right\rfloor$. Si $\alpha^b = n$, entonces hemos terminado. Si $\alpha^b > n$, vamos a $[c_{i+1}, d_{i+1}] = [c_i, \alpha]$; de lo contrario $\alpha^b < n$, y dejamos $[c_{i+1}, d_{i+1}] = [\alpha, d_i]$. Continuamos de esta manera hasta que $|c_i − d_i| \leq 1$. Nosotros, a continuación, aumentar el valor almacenado en la variable $b$ e iniciar el bucle de nuevo. La realización de este bucle por todos los $b \leq log(n)$ finaliza el algoritmo.

Un pseudocódigo de la implementación de este algoritmo se puede encontrar en la página 21 de Dietzelbinger la Primalidad de Pruebas en Polynoial Tiempo. Su complejidad es acerca de $O(log^3(n))$.