imported>Ulanwp: Fehlenden Sprachparameter eingefügt; 1 Datumsparameter konvertiert

2026-04-26T18:15:00Z

Fehlenden Sprachparameter eingefügt; 1 Datumsparameter konvertiert

Neue Seite

Ein '''Primzahltest''' ist ein mathematisches Verfahren, um festzustellen, ob eine gegebene Zahl eine [[Primzahl]] ist oder nicht.

== Praktische Anwendung ==
In der Praxis werden Primzahltests insbesondere bei [[Asymmetrisches Kryptosystem|asymmetrischen Verschlüsselungsverfahren]] in der [[Kryptographie]] eingesetzt. [[Algorithmus|Algorithmen]] wie [[RSA-Kryptosystem|RSA]] benötigen Primzahlen in einer Größenordnung von etwa 1000 Stellen in [[Dualsystem|dualer]] Darstellung. Es ist also unmöglich, diese alle zu berechnen und in einer Liste zu speichern, um bei Bedarf einfach darauf zuzugreifen. Auch die Vorausberechnung einer Teilmenge ist aus sicherheitstechnischen Gründen fragwürdig, da die Liste Angreifern in die Hände fallen könnte. Statt der Verwendung einer bekannten Primzahl rät der Algorithmus (mit ein paar Tricks) eine „beliebige“ Zahl und stellt mit Hilfe eines Primzahltests möglichst schnell fest, ob diese tatsächlich prim ist.

Da „echte“ Primzahltests bei Zahlen dieser Größe zu lange dauern, wird meist ein [[Monte-Carlo-Algorithmus]] verwendet, mit dem in Wirklichkeit gar nicht mit absoluter Sicherheit festgestellt werden kann, ob die gegebene Zahl eine Primzahl ist (man spricht auch von ''probabilistischen Primzahltests''). Es kann dabei aber die Wahrscheinlichkeit, eine [[zusammengesetzte Zahl]] fälschlicherweise für eine Primzahl zu halten, beliebig klein gemacht werden. Zwar würde die Verwendung einer Nicht-Primzahl als kryptographischer Schlüssel eine unsichere Verschlüsselung bedeuten, doch wenn die Wahrscheinlichkeit dafür milliardenmal geringer ist als die, dass Absender und Empfänger der Nachricht gleichzeitig vom Blitz getroffen werden, wird dieses Risiko in Kauf genommen, um das ansonsten sehr sichere Verschlüsselungsverfahren verwenden zu können.

== Bekannte Primzahltest-Verfahren ==
Es gibt zahlreiche Ansätze für Primzahltests:

=== Probedivision ===
{{Hauptartikel|Probedivision}}
Der einfachste Primzahltest ist die Probedivision. Dabei probiert man nacheinander, ob die Zahl <math>n</math> durch eine der Primzahlen <math>p</math> mit <math> 2 \le p \le \sqrt{n}</math> teilbar ist. Wenn nicht, dann ist <math>n</math> eine Primzahl. In der Praxis wird die Probedivision nur für kleine <math>n</math> bis etwa eine [[Million]] eingesetzt. Für größere <math>n</math> sind andere Verfahren effizienter.

=== Sieb des Eratosthenes ===
{{Hauptartikel|Sieb des Eratosthenes}}
Das Sieb des Eratosthenes ist ein Algorithmus, der eine Liste von Primzahlen erzeugt. Da diese Liste bis zu einer frei wählbaren Grenze alle Primzahlen enthält, kann sie für einen Primzahltest verwendet werden. Man überprüft dazu, ob die übergebene Zahl in der Liste ist. Auch dieses Verfahren ist für große Zahlen zu aufwendig und kann daher nicht als Primzahltest verwendet werden.

=== Sieb von Atkin ===
{{Hauptartikel|Sieb von Atkin}}
Das Sieb von Atkin ist ein schneller, moderner Algorithmus zur Bestimmung aller Primzahlen bis zu einer vorgegebenen Grenze. Es ist eine optimierte Version des antiken Sieb des Eratosthenes.
Die Performanz ist bei einem kleinen Limit von z. B. 100 noch etwas langsamer als bei dem Sieb des Eratosthenes, aber je größer das Limit, desto größer ist der Zeitvorteil gegenüber der alten Siebmethode.

=== Probabilistische Primzahltests ===
Die folgenden – in aufsteigender Stärke sortierten – Primzahltests beruhen auf dem kleinen fermatschen Satz und Folgerungen daraus:
{| class="wikitable" cellspace="0"
|- class="hintergrundfarbe5"
|'''Primzahltest''' ||'''beruht auf''' ||'''Art der auftretenden Pseudoprimzahlen'''
|-
|[[Fermatscher Primzahltest]] || [[kleiner fermatscher Satz]] ||[[Fermatsche Pseudoprimzahl]]en
|-
|[[Solovay-Strassen-Test]] || [[Kleiner fermatscher Satz#Folgerung durch Euler|Satz von Euler]] und [[Jacobi-Symbol]] ||[[Eulersche Pseudoprimzahl]]en
|-
|[[Miller-Rabin-Test]] || Satz nach Miller ||[[starke Pseudoprimzahl]]en
|}
Der Miller-Rabin-Test ist ein probabilistischer Primzahltest mit akzeptabler Laufzeit. Für gewisse Bereiche natürlicher Zahlen ist bekannt, wie viele der ersten Primzahlen als Basen benutzt werden müssen, um sogar eine sichere Aussage zu machen, den Algorithmus also deterministisch benutzen zu können (siehe {{OEIS|A014233}}).

=== Weitere Primzahltests, die auf dem kleinen fermatschen Satz beruhen ===
* [[Lucas-Test (Mathematik)|Lucas-Test]] und der speziellere [[Pépin-Test]] zum Prüfen von [[Fermat-Zahl]]en
* [[Lucas-Lehmer-Test]] zum Prüfen von [[Mersenne-Primzahl]]en
* Der APRCL-Test, der 1980 von den Mathematikern [[Leonard Adleman|Leonard '''A'''dleman]], [[Carl Pomerance|Carl '''P'''omerance]], [[Robert Rumely|Robert '''R'''umely]], [[Henri Cohen (Mathematiker)|Henri '''C'''ohen]] und [[Hendrik Lenstra|Hendrik W. '''L'''enstra Jr.]] entwickelt und nach den Initialen der Erfinder benannt wurde, stellt durch Ausschalten der [[Fermatsche Pseudoprimzahl|Fermatschen Pseudoprimzahlen]] eine wesentliche Verbesserung des fermatschen Primzahltests dar.<ref>Vgl. Henri Cohen; Hendrik W. Lenstra, Jr.: [https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1984a/art.pdf ''Primality testing and Jacobi sums.''] In: Mathematics of Computation 42 (1984), Nr. 165, S. 297–330.</ref>

=== AKS-Methode ===
Die [[AKS-Primzahltest|AKS-Methode]] ist ein Primzahltest in [[Polynomialzeit]], der im Jahr [[2002]] von [[Manindra Agrawal]], [[Neeraj Kayal]] und [[Nitin Saxena]] gefunden und nach ihnen benannt wurde.<ref name="AKS">{{cite journal |first=Manindra |last=Agrawal |first2=Neeraj |last2=Kayal |first3=Nitin |last3=Saxena |date=2004 |title=PRIMES is in P |journal=[[Annals of Mathematics]] |volume=160 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |url=https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |language=en}}</ref>
Damit ist geklärt, dass [[#Die Rolle von PRIMES in der Komplexitätstheorie|PRIMES]] in der [[P (Komplexitätsklasse)|Komplexitätsklasse P]] liegt.

== Die Rolle von PRIMES in der Komplexitätstheorie ==
Als ''PRIMES'' bezeichnet man in der [[Informatik]] das Problem der Feststellung, ob eine Zahl prim ist.
Bis ins Jahr 2002 erhoffte man sich in der [[Komplexitätstheorie]] von ihr neue Erkenntnisse in Bezug auf das [[P-NP-Problem]]. Falls P≠NP gilt, muss nach dem [[Ladner-Theorem|Satz von Ladner]] ein Problem in NP\P existieren, welches nicht [[NP-Vollständigkeit|NP-vollständig]] ist.<ref>Richard E. Ladner: ''On the structure of polynomial time reducibility.'' In: ''Journal of the ACM.'' Bd. 22, Nr. 1, 1975, S. 151–171, Corollary 1.1., [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 ACM-Eintrag.]</ref> PRIMES galt als ein potenzieller Kandidat für ein solches Problem.

Dies lag daran, dass PRIMES sowohl in der [[NP (Komplexitätsklasse)|Komplexitätsklasse NP]] als auch in der [[Co-NP|Komplexitätsklasse co-NP]] liegt, und demnach nicht NP-vollständig sein konnte (unter der gängigen Annahme, dass P≠NP). Man kannte vor 2002 jedoch keinen nicht-probabilistischen [[Algorithmus|Lösungsalgorithmus]] mit polynomieller Laufzeit.

== Siehe auch ==
* [[Baillie-PSW-Primzahltest]]

== Weblinks ==
{{Wiktionary}}
* D. J. Bernstein: [https://cr.yp.to/primetests.html ''Distinguishing prime numbers from composite numbers.''] Ein Überblick über verschiedene Primzahltestverfahren.
* [https://de.numberworld.info/primCheck Online Primzahl Prüfer.] Testet Zahlen mit bis zu 15 Dezimalstellen (serverseitig).

== Einzelnachweise ==
<references />

[[Kategorie:Primzahl]]

Primzahltest - Versionsgeschichte

imported>Ulanwp: Fehlenden Sprachparameter eingefügt; 1 Datumsparameter konvertiert