Como o código Rosetta do teste de primalidade AKS é tão simples?

Question

Pule para o final para ver a pergunta alternativa.

A seguir está uma implementação Python do Teste de Primalidade AKS .

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)

Como é possível que eles pegaram esse pseudocódigo muito mais detalhado do algoritmo (que envolve operações polinomiais) e o converteram nesta versão de 10 linhas?

O acima é realmente o teste de primalidade AKS? Peguei em:

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

---

Deixe a entrada ser chamada $n$, não $p$.

O código expand_x_1(n)deve estar computando:

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

Onde $c_i = $ a $i$o valor gerado. O outro código que usa este valor simplesmente testa se$c_i \neq 0 \pmod n$, nesse caso (se verdadeiro) ele retorna Falsepara composto. Senão se para todos$c_i$ valores em $i = 0..\lfloor \dfrac{n}{2} \rfloor + 1$ temos $c_i = 0 \pmod n$, então Trueé retornado.

A recursão mais este teste não se parece em nada com o que compõe o algoritmo AKS. Então, eu esperava que um teórico analítico dos números pudesse explicar a fórmula.

Alternativamente, se você não puder responder ao acima, então:

Como podemos estudar a fórmula para $c_i$; você pode pensar em algum rearranjo que tenha? Por exemplo, talvez os denominadores combinando em subchamadas recursivas que possuem piso etc.

Isso é para que eu não tenha que abrir outra pergunta a respeito dessa fórmula.

---

Por exemplo, modifiquei o código para:

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

Portanto, uma vez que não há falhas quando o executo, posso assumir com certa segurança que "denominadores podem ser combinados" algebricamente, ou seja, há alguma identidade usada que deriva das propriedades básicas do piso .

O que mais podemos dizer e como essa fórmula se relaciona com a aritmética polinomial?

Answer 1

Os números que você rotulou como $c_i$são os coeficientes binomiais $\binom ni$; o código verifica se$\binom ni \equiv 0 \pmod n$ para todos $0 < i \le \frac n2$. Este não é o algoritmo AKS . É o algoritmo de força bruta em tempo exponencial listado no artigo da Wikipedia para motivar o algoritmo AKS.