Metraipolis › archive › dc_2b0d7196fa8b

AKS-Primzahltest — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/AKS-Primzahltest
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-08T05:38:06.560Z
SHA-256 of the archived text
9879bfb649b7193f8a49f3957e05a4e1b09ce51e91d61e91ab2e42fe3e023934
Stable URL of this page
https://metraipolis.com/documento/dc_2b0d7196fa8b

How to cite

AKS-Primzahltest — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/AKS-Primzahltest (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2b0d7196fa8b (Metraipolis archive dc_2b0d7196fa8b, sha256 9879bfb649b7193f8a49f3957e05a4e1b09ce51e91d61e91ab2e42fe3e023934)
BibTeX
@misc{dc2b0d7196fa8b,
  title = {AKS-Primzahltest — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/AKS-Primzahltest},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2b0d7196fa8b; sha256 9879bfb649b7193f8a49f3957e05a4e1b09ce51e91d61e91ab2e42fe3e023934},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/AKS-Primzahltest. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Der AKS-Primzahltest (auch bekannt unter dem Namen Agrawal-Kayal-Saxena-Primzahltest) ist ein deterministischer Algorithmus, der für eine natürliche Zahl in polynomieller Laufzeit feststellt, ob sie prim ist oder nicht. Er wurde von den drei indischen Wissenschaftlern Manindra Agrawal, Neeraj Kayal und Nitin Saxena entwickelt und 2002 in einer Abhandlung mit dem Titel PRIMES is in P (deutsch sinngemäß: Das Primzahl-Problem gehört zur Komplexitätsklasse P) veröffentlicht. Für ihre Arbeit wurden die Forscher 2006 mit dem Gödel- und dem Fulkerson-Preis ausgezeichnet. Der später von anderen verbesserte Algorithmus unterscheidet sich wesentlich von allen vorher bekannten polynomiellen Primalitätsbeweis-Algorithmen: Er baut für den Nachweis der – bezogen auf die Länge der Eingangswerte – polynomiellen Laufzeit auf keinen unbewiesenen Hypothesen (wie beispielsweise der verallgemeinerten Riemannschen Vermutung) auf. Die asymptotische Laufzeit des ursprünglichen Algorithmus ist O ( ( log n ) 7 , 5 + ε ) {\displaystyle {\mathcal {O}}\left((\log n)^{7,5+\varepsilon }\right)} , wobei n {\displaystyle n} die zu testende Zahl ist, O {\displaystyle {\mathcal {O}}} für das Landau-Symbol und ε {\displaystyle \varepsilon } für eine beliebig kleine positive Zahl steht.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «AKS-Primzahltest» — https://de.wikipedia.org/wiki/AKS-Primzahltest
Wikidata Q294284: «primality test» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q294284
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/AKS-Primzahltest?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 263580040, consultata il 2026-10-08T05:07:09.737Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 67fca22cc68123e1d3b444f548454beff1801f8b0409b0b42690edd2ab83f8f7