www.wikidata.de-de.nina.az

Miller Rabin Test Der oder Miller Selfridge Rabin Test kurz MRT ist ein probabilistischer Primzahltest und damit ein Alg

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 , von der man wissen will, ob sie prim ist, und eine weitere Zahl und gibt entweder „zusammengesetzt“ oder „wahrscheinlich prim“ aus. Ist prim, so lautet die Ausgabe immer „wahrscheinlich prim“. Anderenfalls wird in den meisten Fällen „zusammengesetzt“ ausgegeben, aber für manche Paare mit zusammengesetztem ist die Ausgabe trotzdem „wahrscheinlich prim“.

Oft wird zufällig gewählt, der MRT zählt in dieser Form zur Klasse der Monte-Carlo-Algorithmen. Durch wiederholtes Testen mit verschiedenen kann die Wahrscheinlichkeit eines Irrtums beliebig klein gehalten werden. Es gibt deterministische Varianten des MRT, bei denen durch geeignete Wahl der 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 ,, für die der Solovay-Strassen-Test die richtige Ausgabe liefert, werden auch vom MRT richtig erkannt.

Algorithmus Bearbeiten

Es sei eine ungerade Zahl, von der festgestellt werden soll, ob sie eine Primzahl ist. Zuerst wählt man eine Zahl aus der Menge .

Der nächste Schritt ist ein Test, den nur Primzahlen und starke Pseudoprimzahlen (zur Basis ) bestehen. Man berechnet (ungerade) und so, dass

und prüft dann, ob entweder

oder

gilt. Für eine Primzahl ist dies stets der Fall. Wenn die Bedingung nicht erfüllt ist, muss also zusammengesetzt sein. Die Bedingung wird jedoch auch von einigen Zahlenpaaren , mit zusammengesetztem erfüllt, so dass der Test die Zusammengesetztheit von mit diesem nicht zeigt. Dann heißt eine starke Pseudoprimzahl zur Basis .

Funktionsweise Bearbeiten

Man betrachtet die Folge

In der jedes Element das Quadrat seines Vorgängers ist. Die Elemente werden modulo berechnet.

Ist eine Primzahl, dann gilt nach dem kleinen fermatschen Satz

und obige Folge hat deshalb 1 als letztes Element.

Für Primzahlen ist der Vorgänger einer 1 in der Folge immer kongruent zu 1 oder zu -1:

Die Folge besteht dann also entweder nur aus Einsen, oder sie enthält (was sich bei modulo-n-Rechnung für einen Wert kongruent zu −1 ergibt), worauf wegen Einsen folgen. Wenn die Folge nicht diese Form hat, muss zusammengesetzt sein.

Man prüft, ob die Folge mit 1 beginnt oder ob spätestens als vorletztes Element auftritt. Ist dies der Fall, ist entweder prim oder eine starke Pseudoprimzahl zur Basis , und es wird „möglicherweise prim“ ausgegeben. Ansonsten kann nicht prim sein, und der Algorithmus gibt „zusammengesetzt“ aus. Man kann die Berechnung abbrechen, wenn oder ohne vorhergehendes auftritt, denn danach kann nur noch bzw. kommen.

Zuverlässigkeit Bearbeiten

Ist ungerade und nicht prim, so enthält die Menge höchstens Elemente mit , die keine Zeugen für die Zusammengesetztheit von sind. Ist , dann wird immer für ein sein, und wird als zusammengesetzt erkannt.

Ist ein zusammengesetztes ungerades gegeben und wählt man zufällig ein aus , dann ist somit die Wahrscheinlichkeit, dass das Ergebnis „wahrscheinlich prim“ lautet, kleiner als . Wiederholt man den Test mehrfach für verschiedene voneinander unabhängig gewählte aus dieser Menge, sinkt die Wahrscheinlichkeit weiter ab. Nach Schritten ist die Wahrscheinlichkeit, eine zusammengesetzte Zahl für prim zu halten, kleiner als , also z. B. nach vier Schritten kleiner als 0,4 % und nach zehn Schritten kleiner als .

Das ist eine pessimistische Schätzung, die von den „problematischsten“ Werten für ausgeht. Für die meisten zusammengesetzten ist der Anteil der Basen, die ein falsches Ergebnis liefern, erheblich kleiner als , und für viele ist er sogar 0.

Deterministische Varianten Bearbeiten

Der Miller-Rabin-Algorithmus kann deterministisch angewendet werden, indem alle Basen in einer bestimmten Menge getestet werden (Beispiel: wenn n < 9.080.191, dann ist es ausreichend a = 31 und 73 zu testen, siehe unten).

Wenn das getestete zusammengesetzt ist, sind die zu teilerfremden starken Pseudoprimzahlen in einer echten Untergruppe von enthalten. Dies bedeutet, dass beim Testen aller aus einer Menge, die erzeugt, eines der ein Zeuge für das Zusammengesetztsein von ist. Wenn angenommen wird, dass die Riemannsche Vermutung wahr ist, dann folgt daraus, dass die Gruppe durch ihre Elemente kleiner O((log n)2) generiert wird, was bereits im Algorithmus von Miller angeführt wurde. Die Konstante in der Landau-Notation wurde von Eric Bach auf 2 reduziert. Deshalb erhält man einen deterministischen Primzahltest, wenn alle getestet werden. Die Laufzeit dieses Algorithmus ist O((log n)4).

Wenn die Zahl klein ist, ist es nicht notwendig, alle bis zu testen, da bekannt ist, dass eine viel kleinere Anzahl ausreichend ist.

Beispielsweise wurde folgendes verifiziert:

n kleiner als zu testende a Quelle
2.047 2 :1023
1.373.653 2, 3
9.080.191 31, 73 :926
4.759.123.141 2, 7, 61
2.152.302.898.747 2, 3, 5, 7, 11 :916
3.474.749.660.383 2, 3, 5, 7, 11, 13
341.550.071.728.321 2, 3, 5, 7, 11, 13, 17
3.825.123.056.546.413.051 2, 3, 5, 7, 11, 13, 17, 19, 23
318.665.857.834.031.151.167.461 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
3.317.044.064.679.887.385.961.981 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41

Dabei dürfen nur solche getestet werden, die größer sind als das jeweils größte angegebene .

Für das letzte Beispiel ist die Schranke . Daran ist zu erkennen, wie viel eingespart wird, indem nur die Primzahlen bis 41 verwendet werden.

Siehe auch die Prime Pages, Miller-Rabin SPRP bases records, Zhang/Tang und ebenso die Folge A014233 in OEIS zu anderen Kriterien ähnlicher Art. Auf diese Weise hat man sehr schnelle deterministische Primzahltests für Zahlen im geeigneten Bereich, ohne auf unbewiesene Annahmen zurückgreifen zu müssen.

Implementierung Bearbeiten

Diese C++-Implementierung kann alle Zahlen kleiner behandeln: 

#include <cstdint> using u32 = std::uint32_t; using u64 = std::uint64_t; bool mrt (const u32 n, const u32 a) // n ungerade, 1 < a < n-1 {  const u32 m = n - 1;  u32 d = m >> 1, e = 1;  while (!(d & 1))   d >>= 1, ++e;  u64 p = a, q = a;  while (d >>= 1) { // potenziere modular: p = a^d mod n  q *= q; q %= n; // quadriere modular: q = q^2 mod n  if (d & 1)   p *= q, p %= n; // multipliziere modular: p = (p * q) mod n  }  if (p == 1 || p == m)   return true; // n ist wahrscheinlich prim  while (--e) {  p *= p; p %= n;  if (p == m) return true;  if (p <= 1) break;  }  return false; // n ist nicht prim }

Praktische Relevanz Bearbeiten

Primzahltests werden vor allem in der Kryptographie benötigt. Ein typisches Beispiel ist die Schlüsselerstellung für das RSA-Kryptosystem, hierfür werden mehrere große Primzahlen benötigt. Zwar wurde im Jahr 2002 mit dem AKS-Primzahltest erstmals ein beweisbar deterministischer, in polynomialer Zeit laufender Primzahltest vorgestellt. Dessen Laufzeit ist jedoch für praktische Anwendungen meist zu hoch, weswegen für Kryptographie-Software meist immer noch der Miller-Rabin-Test eingesetzt wird. Dabei ist es zwar theoretisch möglich, dass eine zusammengesetzte Zahl als Primzahl genutzt wird, die Wahrscheinlichkeit ist jedoch so gering, dass es in der Praxis keine Rolle spielt.

Literatur Bearbeiten

  • Johannes Buchmann: Einführung in die Kryptographie. 2. Auflage. Springer, 2001, S. 108–111
  • Karpfinger, Kiechle: Kryptologie, Algebraische Methoden und Algorithmen. Vieweg+Teubner, 2010, S. 147–152, mit vollständigen Beweisen

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. M. O. Rabin: Probabilistic algorithms. In: J. F. Traub (ed.): Algorithms and complexity. Academic Press 1976, S. 21–39, speziell S. 35/36, zum Teil nach Ideen von Miller
  2. Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, S. 208–214
  3. Gary L. Miller: Riemann’s Hypothesis and Tests for Primality. In: Journal of Computer and System Sciences 13 (1976), no. 3, pp. 300–317.
  4. Eric Bach: Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), no. 191, pp. 355–380.
  5. Carl Pomerance, John L. Selfridge, Samuel Wagstaff: The pseudoprimes to 25·10⁹. In: Mathematics of Computation. Band 35, 1980, S. 1003–1026, doi:10.1090/S0025-5718-1980-0572872-7 (englisch).
  6. ↑ Gerhard Jaeschke: On strong pseudoprimes to several bases. In: Mathematics of Computation. Band 61, 1993, S. 915–926, doi:10.2307/2153262 (englisch).
  7. Yupeng Jiang and Yingpu Deng: Strong pseudoprimes to the first eight prime bases. In: Mathematics of Computation. Band 83, 2014, S. 2915–2924, doi:10.1090/S0025-5718-2014-02830-5 (englisch).
  8. Jonathan Sorenson, Jonathan Webster: Strong pseudoprimes to twelve prime bases. In: Mathematics of Computation. Band 86, 2017, S. 985–1003, doi:10.1090/mcom/3134, arxiv:1509.00864 [math] (englisch).
  9. Prime Pages der University of Tennessee at Martin
  10. Miller-Rabin SPRP bases records
  11. Zhenxiang Zhang, Min Tang: Finding strong pseudoprimes to several bases. II. In: Math. Comp. 72 (2003), S. 2085–2097
  12. Die Folge A014233 in OEIS
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 erhalt als Eingabe eine ungerade naturliche Zahl n 5 displaystyle n geq 5 von der man wissen will ob sie prim ist und eine weitere Zahl a 2 3 4 n 2 displaystyle a in 2 3 4 dotsc n 2 und gibt entweder zusammengesetzt oder wahrscheinlich prim aus Ist n displaystyle n prim so lautet die Ausgabe immer wahrscheinlich prim Anderenfalls wird in den meisten Fallen zusammengesetzt ausgegeben aber fur manche Paare n a displaystyle n a mit zusammengesetztem n displaystyle n ist die Ausgabe trotzdem wahrscheinlich prim Oft wird a displaystyle a zufallig gewahlt der MRT zahlt in dieser Form zur Klasse der Monte Carlo Algorithmen Durch wiederholtes Testen mit verschiedenen a displaystyle a kann die Wahrscheinlichkeit eines Irrtums beliebig klein gehalten werden Es gibt deterministische Varianten des MRT bei denen durch geeignete Wahl der a displaystyle a ein Irrtum ausgeschlossen wird Der MRT ist nach Gary L Miller und Michael O Rabin benannt 1 John L Selfridge hat diesen Test schon 1974 verwendet bevor Rabin ihn 1976 veroffentlichte Daher ruhrt der alternative Name Miller Selfridge Rabin Test 2 Der MRT funktioniert ahnlich wie der Solovay Strassen Test ist diesem allerdings in allen Aspekten uberlegen Er ist schneller seine Irrtumswahrscheinlichkeit ist geringer und alle Paare n displaystyle n a displaystyle a fur die der Solovay Strassen Test die richtige Ausgabe liefert werden auch vom MRT richtig erkannt Inhaltsverzeichnis 1 Algorithmus 2 Funktionsweise 3 Zuverlassigkeit 4 Deterministische Varianten 5 Implementierung 6 Praktische Relevanz 7 Literatur 8 Weblinks 9 EinzelnachweiseAlgorithmus BearbeitenEs sei n displaystyle n nbsp eine ungerade Zahl von der festgestellt werden soll ob sie eine Primzahl ist Zuerst wahlt man eine Zahl a displaystyle a nbsp aus der Menge 2 3 n 2 displaystyle 2 3 dotsc n 2 nbsp Der nachste Schritt ist ein Test den nur Primzahlen und starke Pseudoprimzahlen zur Basis a displaystyle a nbsp bestehen Man berechnet d displaystyle d nbsp ungerade und j displaystyle j nbsp so dass n 1 d 2 j displaystyle n 1 d cdot 2 j nbsp und pruft dann ob entweder a d 1 mod n displaystyle a d equiv 1 pmod n nbsp oder a d 2 r 1 mod n displaystyle a d cdot 2 r equiv 1 pmod n nbsp fur ein r displaystyle r nbsp mit 0 r lt j displaystyle 0 leq r lt j nbsp gilt Fur eine Primzahl n displaystyle n nbsp ist dies stets der Fall Wenn die Bedingung nicht erfullt ist muss also n displaystyle n nbsp zusammengesetzt sein Die Bedingung wird jedoch auch von einigen Zahlenpaaren n displaystyle n nbsp a displaystyle a nbsp mit zusammengesetztem n displaystyle n nbsp erfullt so dass der Test die Zusammengesetztheit von n displaystyle n nbsp mit diesem a displaystyle a nbsp nicht zeigt Dann heisst n displaystyle n nbsp eine starke Pseudoprimzahl zur Basis a displaystyle a nbsp Funktionsweise BearbeitenMan betrachtet die Folge a d a 2 d a 4 d a 2 j 1 d a 2 j d displaystyle a d a 2d a 4d ldots a 2 j 1 d a 2 j d nbsp In der jedes Element das Quadrat seines Vorgangers ist Die Elemente werden modulo n displaystyle n nbsp berechnet Ist n displaystyle n nbsp eine Primzahl dann gilt nach dem kleinen fermatschen Satz a 2 j d a n 1 1 mod n displaystyle a 2 j d a n 1 equiv 1 pmod n nbsp und obige Folge hat deshalb 1 als letztes Element Fur Primzahlen n displaystyle n nbsp ist der Vorganger einer 1 in der Folge immer kongruent zu 1 oder zu 1 x 2 1 mod n x 2 1 0 mod n n x 2 1 n x 1 x 1 n x 1 oder n x 1 x 1 0 mod n oder x 1 0 mod n x 1 mod n oder x 1 mod n displaystyle begin aligned x 2 equiv 1 pmod n amp Leftrightarrow x 2 1 equiv 0 pmod n amp Leftrightarrow n x 2 1 amp Leftrightarrow n x 1 x 1 amp Leftrightarrow n x 1 quad text oder quad n x 1 amp Leftrightarrow x 1 equiv 0 pmod n quad text oder quad x 1 equiv 0 pmod n amp Leftrightarrow x equiv 1 pmod n quad text oder quad x equiv 1 pmod n end aligned nbsp Die Folge besteht dann also entweder nur aus Einsen oder sie enthalt n 1 displaystyle n 1 nbsp was sich bei modulo n Rechnung fur einen Wert kongruent zu 1 ergibt worauf wegen n 1 2 1 displaystyle n 1 2 equiv 1 nbsp Einsen folgen Wenn die Folge nicht diese Form hat muss n displaystyle n nbsp zusammengesetzt sein Man pruft ob die Folge mit 1 beginnt oder ob n 1 displaystyle n 1 nbsp spatestens als vorletztes Element auftritt Ist dies der Fall ist n displaystyle n nbsp entweder prim oder eine starke Pseudoprimzahl zur Basis a displaystyle a nbsp und es wird moglicherweise prim ausgegeben Ansonsten kann n displaystyle n nbsp nicht prim sein und der Algorithmus gibt zusammengesetzt aus Man kann die Berechnung abbrechen wenn 0 displaystyle 0 nbsp oder 1 displaystyle 1 nbsp ohne vorhergehendes n 1 displaystyle n 1 nbsp auftritt denn danach kann nur noch 0 displaystyle 0 nbsp bzw 1 displaystyle 1 nbsp kommen Zuverlassigkeit BearbeitenIst n 5 displaystyle n geq 5 nbsp ungerade und nicht prim so enthalt die Menge 2 3 n 2 displaystyle 2 3 ldots n 2 nbsp hochstens n 3 4 displaystyle tfrac n 3 4 nbsp Elemente a displaystyle a nbsp mit ggT a n 1 displaystyle operatorname ggT a n 1 nbsp die keine Zeugen fur die Zusammengesetztheit von n displaystyle n nbsp sind Ist g ggT a n gt 1 displaystyle g operatorname ggT a n gt 1 nbsp dann wird immer a x k g mod n displaystyle a x equiv kg pmod n nbsp fur ein k N displaystyle k in mathbb N nbsp sein und n displaystyle n nbsp wird als zusammengesetzt erkannt Ist ein zusammengesetztes ungerades n displaystyle n nbsp gegeben und wahlt man zufallig ein a displaystyle a nbsp aus 2 3 n 2 displaystyle 2 3 ldots n 2 nbsp dann ist somit die Wahrscheinlichkeit dass das Ergebnis wahrscheinlich prim lautet kleiner als 1 4 displaystyle tfrac 1 4 nbsp Wiederholt man den Test mehrfach fur verschiedene voneinander unabhangig gewahlte a displaystyle a nbsp aus dieser Menge sinkt die Wahrscheinlichkeit weiter ab Nach s displaystyle s nbsp Schritten ist die Wahrscheinlichkeit eine zusammengesetzte Zahl fur prim zu halten kleiner als 1 4 s displaystyle tfrac 1 4 s nbsp also z B nach vier Schritten kleiner als 0 4 und nach zehn Schritten kleiner als 10 6 displaystyle 10 6 nbsp Das ist eine pessimistische Schatzung die von den problematischsten Werten fur n displaystyle n nbsp ausgeht Fur die meisten zusammengesetzten n displaystyle n nbsp ist der Anteil der Basen die ein falsches Ergebnis liefern erheblich kleiner als 1 4 displaystyle tfrac 1 4 nbsp und fur viele ist er sogar 0 Deterministische Varianten BearbeitenDer Miller Rabin Algorithmus kann deterministisch angewendet werden indem alle Basen in einer bestimmten Menge getestet werden Beispiel wenn n lt 9 080 191 dann ist es ausreichend a 31 und 73 zu testen siehe unten Wenn das getestete n displaystyle n nbsp zusammengesetzt ist sind die zu n displaystyle n nbsp teilerfremden starken Pseudoprimzahlen a displaystyle a nbsp in einer echten Untergruppe von Z n Z displaystyle left mathbb Z n mathbb Z right nbsp enthalten Dies bedeutet dass beim Testen aller a displaystyle a nbsp aus einer Menge die Z n Z displaystyle left mathbb Z n mathbb Z right nbsp erzeugt eines der a displaystyle a nbsp ein Zeuge fur das Zusammengesetztsein von n displaystyle n nbsp ist Wenn angenommen wird dass die Riemannsche Vermutung wahr ist dann folgt daraus dass die Gruppe durch ihre Elemente kleiner O log n 2 generiert wird was bereits im Algorithmus von Miller angefuhrt wurde 3 Die Konstante in der Landau Notation wurde von Eric Bach auf 2 reduziert 4 Deshalb erhalt man einen deterministischen Primzahltest wenn alle a 2 min n 1 2 ln n 2 displaystyle a in 2 ldots min n 1 lfloor 2 ln n 2 rfloor nbsp getestet werden Die Laufzeit dieses Algorithmus ist O log n 4 Wenn die Zahl n displaystyle n nbsp klein ist ist es nicht notwendig alle a displaystyle a nbsp bis 2 ln n 2 displaystyle 2 ln n 2 nbsp zu testen da bekannt ist dass eine viel kleinere Anzahl ausreichend ist Beispielsweise wurde folgendes verifiziert n kleiner als zu testende a Quelle2 047 2 5 10231 373 653 2 39 080 191 31 73 6 9264 759 123 141 2 7 612 152 302 898 747 2 3 5 7 11 6 9163 474 749 660 383 2 3 5 7 11 13341 550 071 728 321 2 3 5 7 11 13 173 825 123 056 546 413 051 2 3 5 7 11 13 17 19 23 7 318 665 857 834 031 151 167 461 2 3 5 7 11 13 17 19 23 29 31 37 8 3 317 044 064 679 887 385 961 981 2 3 5 7 11 13 17 19 23 29 31 37 41Dabei durfen nur solche n displaystyle n nbsp getestet werden die grosser sind als das jeweils grosste angegebene a displaystyle a nbsp Fur das letzte Beispiel ist die Schranke a 2 ln n 2 6325 displaystyle a leq lfloor 2 cdot ln n 2 rfloor 6325 nbsp Daran ist zu erkennen wie viel eingespart wird indem nur die Primzahlen bis 41 verwendet werden Siehe auch die Prime Pages 9 Miller Rabin SPRP bases records 10 Zhang Tang 11 und ebenso die Folge A014233 12 in OEIS zu anderen Kriterien ahnlicher Art Auf diese Weise hat man sehr schnelle deterministische Primzahltests fur Zahlen im geeigneten Bereich ohne auf unbewiesene Annahmen zuruckgreifen zu mussen Implementierung BearbeitenDiese C Implementierung kann alle Zahlen kleiner 2 32 displaystyle 2 32 nbsp behandeln include lt cstdint gt using u32 std uint32 t using u64 std uint64 t bool mrt const u32 n const u32 a n ungerade 1 lt a lt n 1 const u32 m n 1 u32 d m gt gt 1 e 1 while d amp 1 d gt gt 1 e u64 p a q a while d gt gt 1 potenziere modular p a d mod n q q q n quadriere modular q q 2 mod n if d amp 1 p q p n multipliziere modular p p q mod n if p 1 p m return true n ist wahrscheinlich prim while e p p p n if p m return true if p lt 1 break return false n ist nicht prim Praktische Relevanz BearbeitenPrimzahltests werden vor allem in der Kryptographie benotigt Ein typisches Beispiel ist die Schlusselerstellung fur das RSA Kryptosystem hierfur werden mehrere grosse Primzahlen benotigt Zwar wurde im Jahr 2002 mit dem AKS Primzahltest erstmals ein beweisbar deterministischer in polynomialer Zeit laufender Primzahltest vorgestellt Dessen Laufzeit ist jedoch fur praktische Anwendungen meist zu hoch weswegen fur Kryptographie Software meist immer noch der Miller Rabin Test eingesetzt wird Dabei ist es zwar theoretisch moglich dass eine zusammengesetzte Zahl als Primzahl genutzt wird die Wahrscheinlichkeit ist jedoch so gering dass es in der Praxis keine Rolle spielt Literatur BearbeitenJohannes Buchmann Einfuhrung in die Kryptographie 2 Auflage Springer 2001 S 108 111 Karpfinger Kiechle Kryptologie Algebraische Methoden und Algorithmen Vieweg Teubner 2010 S 147 152 mit vollstandigen BeweisenWeblinks BearbeitenEric W Weisstein Miller Rabin Test In MathWorld englisch Einzelnachweise Bearbeiten M O Rabin Probabilistic algorithms In J F Traub ed Algorithms and complexity Academic Press 1976 S 21 39 speziell S 35 36 zum Teil nach Ideen von Miller Song Y Yan Number theory for computing 2 Auflage Springer 2002 S 208 214 Gary L Miller Riemann s Hypothesis and Tests for Primality In Journal of Computer and System Sciences 13 1976 no 3 pp 300 317 Eric Bach Explicit bounds for primality testing and related problems Mathematics of Computation 55 1990 no 191 pp 355 380 Carl Pomerance John L Selfridge Samuel Wagstaff The pseudoprimes to 25 10 In Mathematics of Computation Band 35 1980 S 1003 1026 doi 10 1090 S0025 5718 1980 0572872 7 englisch a b Gerhard Jaeschke On strong pseudoprimes to several bases In Mathematics of Computation Band 61 1993 S 915 926 doi 10 2307 2153262 englisch Yupeng Jiang and Yingpu Deng Strong pseudoprimes to the first eight prime bases In Mathematics of Computation Band 83 2014 S 2915 2924 doi 10 1090 S0025 5718 2014 02830 5 englisch Jonathan Sorenson Jonathan Webster Strong pseudoprimes to twelve prime bases In Mathematics of Computation Band 86 2017 S 985 1003 doi 10 1090 mcom 3134 arxiv 1509 00864 math englisch Prime Pages der University of Tennessee at Martin Miller Rabin SPRP bases records Zhenxiang Zhang Min Tang Finding strong pseudoprimes to several bases II In Math Comp 72 2003 S 2085 2097 Die Folge A014233 in OEIS Abgerufen von https de wikipedia org w index php title Miller Rabin Test amp oldid 235763320