En quoi le code Rosetta de test de primalité AKS est-il si simple?
Passez à la fin pour voir une autre question.
Voici une implémentation Python du test de primalité 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)
Comment est-il possible qu'ils aient pris ce pseudo-code beaucoup plus approfondi de l'algorithme (qui implique des opérations polynomiales), et l'ont converti dans cette version à 10 lignes?
Est-ce que ce qui précède est vraiment le test de primalité AKS? Je l'ai obtenu de:
https://rosettacode.org/wiki/AKS_test_for_primes#Python
Que l'entrée soit appelée $n$, ne pas $p$.
Le code expand_x_1(n)doit être informatique:
$$c_0 = 1, c_i = \lfloor \dfrac{c_{i-1}(n-i)}{i + 1}\rfloor$$
Où $c_i = $ la $i$e produit de la valeur. L'autre code utilisant cette valeur teste simplement si$c_i \neq 0 \pmod n$, auquel cas (si vrai) il retourne Falsepour composite. Sinon si pour tous$c_i$ valeurs à $i = 0..\lfloor \dfrac{n}{2} \rfloor + 1$ nous avons $c_i = 0 \pmod n$, puis Trueest retourné.
La récursivité et ce test ne ressemblent pas du tout à ce qui compose l'algorithme AKS. J'espérais donc qu'un théoricien analytique des nombres pourrait expliquer la formule.
Sinon, si vous ne pouvez pas répondre à la question ci-dessus, alors:
Comment pouvons-nous étudier la formule pour $c_i$; pouvez-vous penser à des réarrangements qu'il a? Comme peut-être les dénominateurs se combinant à travers les sous-appels récursifs qui ont un plancher, etc.
C'est pour ne pas avoir à ouvrir une autre question concernant cette formule.
Par exemple, j'ai modifié le code pour:
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
Par conséquent, comme il n'obtient aucun échec lorsque je l'exécute, je peux supposer en toute sécurité que «les dénominateurs peuvent être combinés» algébriquement, c'est-à-dire qu'il y a une certaine identité utilisée qui dérive des propriétés de base de floor .
Que pouvons-nous dire d'autre et comment cette formule se rapporte-t-elle à l'arithmétique polynomiale?
Réponses
Les nombres que vous avez étiquetés comme $c_i$sont les coefficients binomiaux $\binom ni$; le code vérifie si$\binom ni \equiv 0 \pmod n$ pour tous $0 < i \le \frac n2$. Ce n'est pas l'algorithme AKS . C'est l'algorithme de force brute à temps exponentiel répertorié dans l'article de Wikipédia pour motiver l'algorithme AKS.