Miller-Rabin-Test

Der Miller-Rabin-Test oder Miller-Selfridge-Rabin-Test (kurz MRT) ist ein probabilistischer Primzahltest und damit ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie, insbesondere der algorithmischen Zahlentheorie.

Der MRT erhält als Eingabe eine ungerade natürliche Zahl ${\displaystyle n\geq 5}$, von der man wissen will, ob sie prim ist, und eine weitere Zahl ${\displaystyle a\in \{2,3,4,\dotsc ,n-2\}}$ und gibt entweder „zusammengesetzt“ oder „wahrscheinlich prim“ aus. Ist ${\displaystyle n}$ prim, so lautet die Ausgabe immer „wahrscheinlich prim“. Anderenfalls wird in den meisten Fällen „zusammengesetzt“ ausgegeben, aber für manche Paare ${\displaystyle n,a}$ mit zusammengesetztem ${\displaystyle n}$ ist die Ausgabe trotzdem „wahrscheinlich prim“.

Oft wird ${\displaystyle a}$ zufällig gewählt, der MRT zählt in dieser Form zur Klasse der Monte-Carlo-Algorithmen. Durch wiederholtes Testen mit verschiedenen ${\displaystyle a}$ kann die Wahrscheinlichkeit eines Irrtums beliebig klein gehalten werden. Es gibt deterministische Varianten des MRT, bei denen durch geeignete Wahl der ${\displaystyle a}$ ein Irrtum ausgeschlossen wird.

Der MRT ist nach Gary L. Miller und Michael O. Rabin benannt. John L. Selfridge hat diesen Test schon 1974 verwendet, bevor Rabin ihn 1976 veröffentlichte. Daher rührt der alternative Name Miller-Selfridge-Rabin-Test.

Der MRT funktioniert ähnlich wie der Solovay-Strassen-Test, ist diesem allerdings in allen Aspekten überlegen. Er ist schneller, seine Irrtumswahrscheinlichkeit ist geringer, und alle Paare ${\displaystyle n}$,${\displaystyle a}$, für die der Solovay-Strassen-Test die richtige Ausgabe liefert, werden auch vom MRT richtig erkannt.