Dlaczego kod Rosetta testu pierwotności AKS jest taki prosty?

Nov 24 2020

Przejdź do końca, aby zobaczyć alternatywne pytanie.

Poniżej przedstawiono implementację testu pierwszości AKS w języku Python .

from sympy import *

def expand_x_1(n): 
    # This version uses a generator and thus less computations
    c = 1
    for i in range(n//2 + 1):       # // means flooring after divide
        c = c*(n - i)//(i + 1)
        yield c

def aks(p):
    if p==2:
        return True

    for i in expand_x_1(p):
        if i % p:
            # we stop without computing all possible solutions
            return False
    return True


for n in range(2, 10000):
    primality = aks(n)
    primality1 = isprime(n)
    if primality != primality1:
        print("Fails @", n)  # Never prints
        assert (0)
    else:
        print(primality)

Jak to możliwe, że wzięli o wiele bardziej szczegółowy pseudokod algorytmu (który obejmuje operacje wielomianowe) i przekonwertowali go na tę 10-liniową wersję?

Czy powyższe naprawdę jest testem pierwszości AKS? Dostałem od:

https://rosettacode.org/wiki/AKS_test_for_primes#Python


Niech zostanie wywołane wejście $n$, nie $p$.

Kod w expand_x_1(n)musi być obliczany:

$$c_0 = 1, c_i = \lfloor \dfrac{c_{i-1}(n-i)}{i + 1}\rfloor$$

Gdzie $c_i = $ the $i$uzyskana wartość. Drugi kod używający tej wartości po prostu sprawdza, czy$c_i \neq 0 \pmod n$, w takim przypadku (jeśli prawda) zwraca wartość Falsezłożoną. Inaczej, jeśli dla wszystkich$c_i$ wartości w $i = 0..\lfloor \dfrac{n}{2} \rfloor + 1$ mamy $c_i = 0 \pmod n$, a następnie Truejest zwracany.

Rekursja oraz ten test nie wydają się w ogóle tym, co składa się na algorytm AKS. Miałem więc nadzieję, że analityczny teoretyk liczb może wyjaśnić wzór.

Alternatywnie, jeśli nie możesz odpowiedzieć na powyższe, to:

Jak możemy przestudiować wzór $c_i$; czy możesz pomyśleć o jakichś jego przegrupowaniach? Na przykład mianowniki łączące się w rekurencyjnych wywołaniach podrzędnych, które mają podłogę itp.

Dlatego nie muszę otwierać kolejnego pytania dotyczącego tej formuły.


Na przykład zmodyfikowałem kod, aby:

def expand_x_1(n): 
   c = 1
   d = 1
   for i in range(n//2 + 1):
       d *= (i + 1)
       c = c*(n - i)
       yield c//d

Dlatego też, ponieważ nie ma żadnych błędów, kiedy go uruchamiam, mogę w pewnym stopniu bezpiecznie założyć, że „mianowniki można łączyć” algebraicznie, tj. Istnieje pewna tożsamość, która wywodzi się z podstawowych właściwości podłogi .

Co jeszcze możemy powiedzieć i jak ten wzór odnosi się do arytmetyki wielomianowej?

Odpowiedzi

3 AndersKaseorg Nov 24 2020 at 11:53

Liczby, które oznaczyłeś jako $c_i$są współczynnikami dwumianu $\binom ni$; kod sprawdza, czy$\binom ni \equiv 0 \pmod n$ dla wszystkich $0 < i \le \frac n2$. To nie jest algorytm AKS . Jest to algorytm brutalnej siły w czasie wykładniczym wymieniony w artykule Wikipedii w celu motywowania algorytmu AKS.