PDF herunterladen
PDF herunterladen
Primzahlen sind Zahlen, die nur durch sich selbst und 1 teilbar sind - die anderen Zahlen werden zusammengesetzte Zahlen genannt. Zum Testen, ob eine Zahl eine Primzahl ist, gibt es viele Methoden. Einerseits gibt es Tests, die perfekt sind, aber extrem langsam bei großen Zahlen. Andererseits gibt es sehr viel schnellere Tests, aber sie führen manchmal zu falschen Ergebnissen. Hier sind ein paar Methoden, von denen man wählen kann, abhängig von der Größe der zu prüfenden Zahl.
Vorgehensweise
‘‘‘Beachte:‘‘‘ In allen Formeln ist ‘‘n‘‘ die zu prüfende Zahl.
-
Versuchsweises Teilen. Teile ‘‘n‘‘ durch alle Primzahlen von 2 bis zum Limit ( ).
-
Mit Hilfe des Kleinen Satzes von Fermat. Warnung: Falsche Ergebnisse sind möglich.
- Wähle einen ganzzahligen Wert für ‘‘a‘‘ wie etwa 2 ≤ a ≤ n - 1.
- Wenn a n (mod n) = a (mod n), dann ist ‘’n’’ wahrscheinlich eine Primzahl. Wenn dies nicht wahr ist, dann ist ‘‘n‘‘ keine Primzahl.
- Wiederhole das Ganze mit verschiedenen Werten für ‘‘a‘‘, um die Zuverlässigkeit der Primalität zu erhöhen.
-
Mit Hilfe des Miller-Rabin-Tests. Warnung: Falsche Ergebnisse sind möglich, selten aber für mehrfache Werte von ‘‘a‘‘.
- Finde Werte für s und d, wie .
- Wähle eine ganze Zahl wie 2 ≤ a ≤ n - 1.
- Wenn a d = +1 (mod n) or -1 (mod n), dann ist n wahrscheinlich keine Primzahl.Springe zum Testergebnis. Anderenfalls mache mit dem nächsten Schritt weiter.
- Quadriere dein Ergebnis ( ). Wenn dies gleich +1 (mod n) or -1 (mod n) ist, springe zum Testergebnis. Anderenfalls wiederhole ( etc.) bis .
- Testergebnis:Wenn n den Test besteht, wiederhole das Ganze mit verschiedenen Werten für ‘‘a‘‘, um die Zuverlässigkeit der Primalität zu erhöhen.
Werbeanzeige
-
Verstehe die Teilungsmethode. Primzahlen sind entsprechend ihrer Definition nur Primzahlen, wenn ‘‘n‘‘ nicht durch 2 oder eine größere ganze Zahl geteilt werden kann. Die gegebene Formel ist zeitsparend, indem sie unnötige Versuche ausschließt (beispielsweise muss nicht mehr mit 9 geprüft werden, wenn man schon mit 3 geprüft hat).
- Die Höchstzahl (x) wird auf nächste ganze Zahl ≥ x runden.
-
Verstehe modulare Arithmetik. Die Operation "x mod y" bedeutet: Teile x durch y und finde den Rest. [1] X Forschungsquelle Anders ausgedrückt, in modularer Arithmetik gehen Zahlen wieder auf Null zurück, sobald sie einen bestimmten Wert, den ‘‘Modulus‘‘, erreicht haben. Dementsprechend zählt eine Uhr bis 12: sie geht von 10 zu 11 zu 12, dann wieder zurück auf 1.
- Viele Rechner haben eine mod-Taste, aber sieh am Ende dieses Abschnitts nach, um zu sehen, wie man dieses Problem bei großen Zahlen löst.
-
Kenne die Fallen vom Kleinen Satz von Fermat. Alle Zahlen, die diesen Test nicht bestehen, sind zusammengesetzte Zahlen (Nicht-Primzahlen), jedoch sind die Zahlen, die den Test bestehen, nur ‘‘wahrscheinliche‘‘ Primzahlen. Um sicherzugehen, dass du falsche Ergebnisse vermeidest, suche ‘‘n‘‘ in einer Liste von „Carmichael Zahlen“ (die den Test immer bestehen) und „Fermat Pseudo-Primzahlen“ (welche den Test nur bei einigen Werten von a bestehen) [2] X Forschungsquelle
-
Verwende den Miller-Rabin-Test, wenn immer es möglich ist. Obwohl es mühselig ist, ihn von Hand durchzuführen, wird dieser Test im Allgemeinen von Software benutzt. Dies kann ziemlich schnell durchgeführt werden und führt zu weniger falschen Ergebnissen als Fermat’s Methode. [3] X Forschungsquelle Eine zusammengesetzte Zahl gibt nie ein falsches Ergebnis für mehr als einem Viertel aller Werte von a. [4] X Forschungsquelle Wenn du mehrere zufällige Werte für a wählst und sie alle den Test bestehen, kannst du ziemlich sicher sein, dass n eine Primzahl ist.
-
Wende modulare Arithmetik bei großen Zahlen an. Solltest du keinen Rechner mit mod-Funktion haben, oder sollte dein Rechner solch große Zahlen nicht anzeigen können, verwende Potenzen und die modulare Arithmetik, um den Vorgang zu vereinfachen. [5] X Forschungsquelle hier ist ein Beispiel für mod 50:
- Schreibe den Ausdruck in überschaubarere Potenzen um: mod 50. (Wenn du von Hand rechnest, wirst du den Ausdruck weiter zerlegen müssen.)
- mod 50 = mod 50 mod 50) mod 50.
- mod 50 = 43.
- mod 50 mod 50) mod 50 = mod 50
- mod 50
Werbeanzeige
-
Wähle zwei Zahlen. Eine der Zahlen ist keine Primzahl und die andere ist die zu testende Zahl.
- "Zahl1" = 35
- Zahl2 = 97
-
Wähle zwei Punkte, die größer als Null und jeweils kleiner als Zahl1 und Zahl2 sind. Sie dürfen nicht gleich sein.
- Punkt1 = 1
- Punkt2 = 2
-
Berechne die MMI (Mathematische Multiplikative Inverse) für Zahl1 und Zahl2.
- Berechne die MMI
- MMI1 = Zahl2 -1 mod Zahl1
- MMI2 = Zahl1 -1 mod Zahl2
- Das gilt nur für Primzahlen (es kommt zwar auch eine Zahl als Ergebnis heraus bei Nicht-Primzahlen, aber das ist dann nicht die MMI):
- MMI1 = (Zahl2 Zahl1-2 ) mod Zahl1
- MMI2 = (Zahl1 Zahl2-2 ) mod Zahl2
- Zum Beispiel
- MMI1 = (97 33 ) mod 35
- MMI2 = (35 95 ) mod 97
- Berechne die MMI
-
Erstelle eine Binärtabelle für jede MMI bis zu Log2 des Modulos
- Für MMI1
- F(1) = Zahl2 mod Zahl1 = 97 mod 35 = 27
- F(2) = F(1) * F(1) mod Zahl1 = 27 * 27 mod 35 = 29
- F(4) = F(2) * F(2) mod Zahl1 = 29 * 29 mod 35 = 1
- F(8) = F(4) * F(4) mod Zahl1 = 1 * 1 mod 35 = 1
- F(16) =F(8) * F(8) mod Zahl1 = 1 * 1 mod 35 = 1
- F(32) =F(16) * F(16) mod Zahl1 = 1 * 1 mod 35 = 1
- Berechne die Binärdarstellung von Zahl1 - 2
- 35 -2 = 33 (10001) Basis 2
- MMI1 = F(33) = F(32) * F(1) mod 35
- MMI1 = F(33) = 1 * 27 mod 35
- MMI1 = 27
- Für MMI2
- F(1) = Zahl1 mod Zahl2 = 35 mod 97 = 35
- F(2) = F(1) * F(1) mod Zahl2 = 35 * 35 mod 97 = 61
- F(4) = F(2) * F(2) mod Zahl2 = 61 * 61 mod 97 = 35
- F(8) = F(4) * F(4) mod Zahl2 = 35 * 35 mod 97 = 61
- F(16) = F(8) * F(8) mod Zahl2 = 61 * 61 mod 97 = 35
- F(32) = F(16) * F(16) mod Zahl2 = 35 * 35 mod 97 = 61
- F(64) = F(32) * F(32) mod Zahl2 = 61 * 61 mod 97 = 35
- F(128) = F(64) * F(64) mod Zahl2 = 35 * 35 mod 97 = 61
- Berechne die Binärdarstellung von Zahl2 - 2
- 97 - 2 = 95 = (1011111) Basis 2
- MMI2 = (((((F(64) * F(16) mod 97) * F(8) mod 97) * F(4) mod 97) * F(2) mod 97) * F(1) mod 97)
- MMI2 = (((((35 * 35) mod 97) * 61) mod 97) * 35 mod 97) * 61 mod 97) * 35 mod 97)
- MMI2 = 61
- Für MMI1
-
Berechne (Punkt1 * Zahl2 * MMI1 + Punkt2 * Zahl1 * MMI2) mod (Zahl1 * Zahl2)
- Ergebnis = (1 * 97 * 27 + 2 * 35 * 61) mod (97 * 35)
- Ergebnis = (2619 + 4270) mod 3395
- Ergebnis = 99
-
Verifiziere, dass "Zahl1" nicht prim ist.
- Berechne (Ergebnis - Punkt1) mod Zahl1
- 99 -1 mod 35 = 28
- Da 28 größer als Null ist, ist 35 nicht prim.
-
Überprüfe, ob Zahl2 prim ist.
- Berechne (Ergebnis - Punkt2) mod Zahl2
- 99 - 2 mod 97 = 0
- Da 0 gleich 0, ist 97 möglicherweise prim.
-
Wiederhole die Schritte 1 bis 7 mindestens noch zweimal.
- Wenn Schritt 7 Null ist:
- Verwende eine andere Zahl für "Zahl1", die nicht prim ist.
- Verwende eine andere Zahl für "Zahl1", die prim ist. In diesem Fall sollte das Ergebnis von Schritt 6 und 7 Null sein.
- Verwende andere Zahlen für Punkt1 und Punkt2.
- Wenn das Ergebnis von Schritt 7 immer 0 ist, dann ist die Wahrscheinlichkeit sehr hoch, dass Zahl2 prim ist.
- Die Schritte 1 bis 7 funktionieren manchmal nicht, wenn die erste Zahl nicht prim ist und die zweite Zahl ein Teiler von "Zahl1" ist. Es funktioniert immer, wenn beide Zahlen prim sind.
- Der Grund, warum die Schritte 1 bis 7 wiederholt werden, ist, weil es ein paar Szenarios gibt, in denen, selbst wenn Zahl1 nicht prim ist und Zahl2 nicht prim ist, das Ergebnis von Schritt 7 trotzdem Null ist bei einer oder beiden Zahlen. Diese Umstände sind selten. Wenn wir für Zahl1 eine andere Zahl, die nicht prim ist, wählen, dann erhalten wir für Zahl2 schnell ein Ergebnis in Schritt 7, das nicht Null ist. Außer in diesem Fall erhalten wir immer Null als Ergebnis bei Primzahlen in Schritt 7.
Werbeanzeige - Wenn Schritt 7 Null ist:
Tipps
- Die 168 Primzahlen kleiner als 1000 sind: 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 [6] X Forschungsquelle
- Die versuchsweise Division ist zwar bei großen Zahlen langsamer als bei etwas verfeinerteren Methoden, aber bei kleinen Zahlen ist es trotzdem noch ziemlich effizient. Selbst beim Testen von großen Zahlen ist es nicht unüblich, zuerst kleinere Teiler auszuprobieren, bevor man zu einer fortgeschritteneren Methode wechselt, wenn keine kleinen Teiler gefunden werden.
Werbeanzeige
Was du brauchst
- Handwerkszeug, wie Papier und Stift oder einen Computer
Referenzen
- ↑ http://betterexplained.com/articles/fun-with-modular-arithmetic/
- ↑ http://mathworld.wolfram.com/FermatsLittleTheorem.html
- ↑ http://www.cs.cornell.edu/courses/cs4820/2010sp/handouts/MillerRabin.pdf
- ↑ https://books.google.com/books?id=QbVtCQAAQBAJ&dq=miller-rabin+1/4+false+positives
- ↑ https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation
- ↑ Online Encyclopedia of Integer Sequences, A000040
Über dieses wikiHow
Diese Seite wurde bisher 44.241 mal abgerufen.
Werbeanzeige
Melde dich für den kostenlosen wikiHow Newsletter an!
Du erhältst hilfreiche Tipps und Anleitungen jede Woche direkt in deine Inbox.
Registriere mich!
