Jak sprawdzić, czy liczba jest idealną potęgą w czasie wielomianowym

23

Pierwszym krokiem algorytmu testowania pierwotności AKS jest sprawdzenie, czy liczba wejściowa jest mocą doskonałą. Wydaje się, że jest to dobrze znany fakt w teorii liczb, ponieważ artykuł nie wyjaśnił go szczegółowo. Czy ktoś może mi powiedzieć, jak to zrobić w czasie wielomianowym? Dzięki.

ds.algorithms nt.number-theory

— yzll
źródło

7

Pierwszym krokiem algorytmu AKS jest sprawdzenie, czy numer wejściowy jest doskonała moc (liczba z formą

pewnego liczb całkowitych C, N> 1), która różni się od badań, czy liczba jest liczbą pierwszą mocy. Testem na doskonałą moc jest ćwiczenie 9.44 książki cytowanej w artykule ( Modern Computer Algebra autorstwa von zur Gathen i Gerhard, 2003). Nie przeczytałem książki i nie znam odpowiedzi, ale skonsultowałeś się z nią?

c^{n}

$c^n$

— Tsuyoshi Ito,

1

Uważam, że pierwszy krok AKS sprawdza, czy liczba jest potęgą jakiejś dodatniej liczby całkowitej, niekoniecznie liczbą pierwszą. Gdyby wiadomo było, jak sprawdzić moc pierwotną w czasie wielomianowym przed AKS, dałoby to już test wieloznaczności pierwotności czasu.

— arnab 10.10.10

@Tsuyoshi Dzięki za zwrócenie uwagi na mój błąd. Nie skonsultowałem książki.

— yzll,

2

Jeśli zależy Ci na pytaniu , spróbuj rozwiązać problem przed jego opublikowaniem.

— Tsuyoshi Ito,

Tsuyoshi / arnab, może powinieneś repost jako odpowiedzi, aby można to zaakceptować?

— Suresh Venkat

31

Biorąc pod uwagę liczbę n, jeśli w ogóle można go zapisać jako (b> 1), a następnie . I dla każdej ustalonej , sprawdzenie czy istnieje z można zrobić za pomocą wyszukiwania binarnego. Chyba całkowity czas pracy to . $a^b$ $b < \log(n) + 1$ $b$ $a$ $a^b = n$ $O(\log^2 n)$

— Ramprasad
źródło

5

Ramprasad za odpowiedź pomija czasie wykonać potęgowanie który

. Innym sposobem jest wybór

następnie obliczyć

th pierwiastek

, które mają całkowity czas

.

O (l o g^{3} n)

$O(log^3 n)$

b

$b$

b

$b$

n

$n$

O (l o g^{3} n)

$O(log^3 n)$

— David Marquis

1

Poprawę prosty, że ponadto usuwa

współczynnik tylko przez wybrał doskonałą

.

\log \log n

$\log \log n$

b

$b$

— Chao Xu,

16

Zobacz Bach i Sorenson, Algorytmy Sieve dla doskonałego testowania mocy, Al Algorytmica 9 (1993), 313-328, DOI: 10.1007 / BF01228507 i DJ Bernstein, Wykrywanie doskonałych mocy w zasadniczo liniowym czasie, Matematyka. Komp. 67 (1998), 1253-1283.

— Jeffrey Shallit
źródło

Jest też praca uzupełniająca z ulepszonym asymptotycznym czasem pracy i prostszym traktowaniem: DJ Bernstein, HW Lenstra Jr. i J. Pila, Wykrywanie doskonałych mocy poprzez uwzględnienie w matematyce. Komp. 76 (2007) 385–388.

— Erick Wong,

3

W artykule znalazłem ciekawe i eleganckie rozwiązanie: o wdrożeniu testu pierwszorzędności klasy AKS, autorstwa R. Crandalla i J. Papadopoulosa, 18 marca 2003 r.

— Plomb
źródło

2

Jakoś mogę pokazać, że algorytmem wyszukiwania binarnego jest . $O(lg~n \cdot (lg~lg~n)^2)$

Po pierwsze, , jest . Algorytm wyszukiwania binarnego: Dla każdego używamy wyszukiwania binarnego, aby znaleźć . $a^b = n$ $b<lg~n$
$b$ $a$

Za każdym razem, obliczanie kosztów operacji za pomocą szybkiej potęgowanie . Dlatego pozostałym problemem jest zakres . $a^b$ $lg~b = lg~lg~n$ $a$

Jeśli jest maksymalna możliwa wartość , a następnie przeszukiwanie binarne musi operacji $A$ $a$ $lg~A$

Zauważ, że , to znaczy $b~lg~a = lg~n$ Podsumowując,

l g A = \frac{l g n}{b}

$lg~A = \frac{lg~n}{b}$

\sum l g A = l g n \cdot (\frac{1}{1} + \frac{1}{2} + . . . + \frac{1}{B}) = l g n \cdot l g B = l g n \cdot l g l g n

$\sum lg~A = lg~n \cdot (\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{B}) = lg~n \cdot lg~B = lg~n \cdot lg~lg~n$

$O(lg~n \cdot lg~lg~n)$

$a^b$ $O(lg~n \cdot (lg~lg~n)^2)$

ps: Wszystkie lg są podstawą 2.

Kod 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
źródło