AKS nombres Premiers algorithme en Python

Il y A quelques années, il a été prouvé que Nombres PREMIERS est en P. Existe-il des algorithmes de mise en œuvre de leur test de primalité en Python? Je voulais courir quelques repères avec une naïveté générateur et de voir par moi-même comment il est rapide. J'aimerais mettre en œuvre moi-même, mais je ne comprends pas le papier encore assez pour le faire.

  • AKS est d'une grande importance théorique, mais sa performance est terrible (de Miller-Rabin est beaucoup mieux). Il existe de nombreux tests de primalité implémenté en Python.
  • Désolé de vous décevoir, mais il y a un peu de mathématique de malentendu ici! Bien que nous n'avons pas formellement établi si P == NP, mais même si P != NP, il ne s'ensuit pas que P == Fast!
InformationsquelleAutor Claudiu | 2008-12-07
  1. 52

    Rapide réponse: non, l'AKS test n'est pas le moyen le plus rapide pour tester la primalité. Il y a beaucoup beaucoup plus rapide tests de primalité que soit assumer le (généralisée) hypothèse de Riemann et/ou sont aléatoires. (E. g. De Miller-Rabin est simple et rapide à mettre en œuvre.) La véritable percée de la papier a été théorique, ce qui prouve un déterministe polynomiale en temps de l'algorithme existe pour le test de primalité, sans présumer de la GRH ou d'autres plaidoiries des conjectures.

    Cela dit, si vous voulez comprendre et de l'appliquer, Scott Aaronson court article pourrait aider. Il n'est pas aller dans tous les détails, mais vous pouvez commencer à la page 10 de 12, et il donne assez. 🙂
    Il y a aussi un liste des implémentations (surtout en C++) ici.

    Aussi, pour l'optimisation et l'amélioration (de plusieurs ordres de grandeur), vous voudrez peut-être regarder à ce rapport, ou (plus) Crandall et Papadopoulos rapport de l', ou (encore plus vieux) Daniel J Bernstein rapport. Tous ont assez détaillée pseudo-code qui se prête bien à la mise en œuvre.

    • Mise à jour: une Autre bonne exposition des mathématiques,par Terence Tao, ici: terrytao.wordpress.com/2009/08/11/the-aks-primality-test
    • L'AKS-Test n'est pas le moyen le plus rapide, mais c'est la première épreuve test pour les nombres premiers.
    • Plus précisément, c'est le premier test que nous pouvons prouver est infaillible et polynôme de temps. Il existe d'autres tests laquelle nous croyons fermement est en fait parfaitement à toute épreuve (par exemple parce qu'il est possible de les prouver en supposant fortement cru en conjectures comme l'Hypothèse de Riemann), et il y a aussi d'autres tests que l'on peut prouver sont parfaitement infaillible, et qui presque toujours courir vite, mais que nous ne pouvons pas prouver sont polynomiaux en temps. La percée de l'AKS était en train de faire à la fois.
    • clairement, vous avez regardé le numberphile vidéo, qui est très trompeur. Il n'est pas le moyen le plus rapide, n'est pas la première épreuve de test, n'est-ce pas le plus rapide épreuve d'essai, etc. Il est déterministe polynomial en temps, que nous n'avions pas avant, sans prendre le ERH. Nous avons eu (et toujours aujourd'hui) AVR-CL qui est effectivement temps polynomial pour n'importe quelle entrée nous serons en informatique. Nous avons eu, et encore utiliser, ECPP qui devrait polynomial en temps (mais peut s'exécuter lentement en raison de l'aléatoire). Les deux sont des "infaillible" méthodes et sont beaucoup plus rapides.
    InformationsquelleAutor ShreevatsaR
  2. -5

    Oui, aller chercher à AKS test pour les nombres premiers page sur rosettacode.org

    def expand_x_1(p):
    ex = [1]
    for i in range(p):
        ex.append(ex[-1] * -(p-i) / (i+1))
    return ex[::-1]

def aks_test(p):
    if p < 2: return False
    ex = expand_x_1(p)
    ex[0] += 1
    return not any(mult % p for mult in ex[0:-1])
    print('# p: (x-1)^p for small p')
    for p in range(12):
        print('%3i: %s' % (p, ' '.join('%+i%s' % (e, ('x^%i' % n) if n else '')
                                   for n,e in enumerate(expand_x_1(p)))))

print('\n# small primes using the aks test')
print([p for p in range(101) if aks_test(p)])

    et la sortie est:

    # p: (x-1)^p for small p
0: +1
1: -1 +1x^1
2: +1 -2x^1 +1x^2
3: -1 +3x^1 -3x^2 +1x^3
4: +1 -4x^1 +6x^2 -4x^3 +1x^4
5: -1 +5x^1 -10x^2 +10x^3 -5x^4 +1x^5
6: +1 -6x^1 +15x^2 -20x^3 +15x^4 -6x^5 +1x^6
7: -1 +7x^1 -21x^2 +35x^3 -35x^4 +21x^5 -7x^6 +1x^7
8: +1 -8x^1 +28x^2 -56x^3 +70x^4 -56x^5 +28x^6 -8x^7 +1x^8
9: -1 +9x^1 -36x^2 +84x^3 -126x^4 +126x^5 -84x^6 +36x^7 -9x^8 +1x^9
10: +1 -10x^1 +45x^2 -120x^3 +210x^4 -252x^5 +210x^6 -120x^7 +45x^8 -10x^9 +1x^10
11: -1 +11x^1 -55x^2 +165x^3 -330x^4 +462x^5 -462x^6 +330x^7 -165x^8 +55x^9 -11x^10 +1x^11
# small primes using the aks test
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    • Ce n'est pas l'algorithme AKS; c'est un exponentielle-temps algorithme qui implémente l'élémentaire idée de l'algorithme AKS avec aucune des idées qui le rend polynôme de temps.
    InformationsquelleAutor Jacques