Inhalt

• Schritte
• Teil 1 von 3: Tests der Einfachheit
• Teil 2 von 3: Wie Einfachheitstests funktionieren
• Teil 3 von 3: Verwendung des chinesischen Restsatzes
• Tipps
• Was brauchst du

Primzahlen sind Zahlen, die nur durch sich selbst und durch 1 teilbar sind. Alle anderen Zahlen heißen zusammengesetzte Zahlen. Es gibt viele Möglichkeiten, um zu bestimmen, ob eine Zahl eine Primzahl ist, und alle haben ihre eigenen Vor- und Nachteile. Einerseits sind einige der Methoden sehr genau, aber bei großen Zahlen recht komplex. Auf der anderen Seite gibt es deutlich schnellere Wege, die jedoch zu falschen Ergebnissen führen können. Die Wahl der geeigneten Methode hängt davon ab, wie groß die Zahlen sind, mit denen Sie arbeiten.

Schritte

Teil 1 von 3: Tests der Einfachheit

Notiz: in allen Formeln n bezeichnet die zu prüfende Nummer.

1. 1 Aufzählung von Teilern. Es reicht zu teilen n auf alle Primzahlen von 2 bis zum gerundeten Wert (${ displaystyle { sqrt {n}}}$).
2. 2 Der kleine Satz von Fermat. Achtung: Manchmal identifiziert der Test zusammengesetzte Zahlen fälschlicherweise als Primzahlen, sogar für alle Werte von a.
   • Wählen wir eine ganze Zahl einmit 2 ≤ a ≤ n - 1.
   • Wenn a (mod n) = a (mod n) ist, ist die Zahl wahrscheinlich eine Primzahl. Wenn die Gleichheit nicht erfüllt ist, ist die Zahl n zusammengesetzt.
   • Gegebene Gleichheit auf mehrere Werte prüfen einum die Wahrscheinlichkeit zu erhöhen, dass die getestete Zahl tatsächlich eine Primzahl ist.
3. 3 Miller-Rabin-Test. Warnung: Manchmal, wenn auch selten, identifiziert der Test für mehrere Werte von a zusammengesetzte Zahlen fälschlicherweise als Primzahlen.
   • Finden Sie die Größen s und d so, dass ${ Displaystil n-1 = 2 ^ {s} * d}$.
   • Wählen Sie eine ganze Zahl ein im Bereich 2 ≤ a ≤ n - 1.
   • Wenn a = +1 (mod n) oder -1 (mod n) ist, dann ist n wahrscheinlich prim. Gehen Sie in diesem Fall zum Testergebnis. Wenn die Gleichheit nicht gilt, fahren Sie mit dem nächsten Schritt fort.
   • Quadrieren Sie Ihre Antwort (${ displaystyle a ^ {2d}}$). Wenn Sie -1 (mod n) erhalten, ist n wahrscheinlich eine Primzahl. Gehen Sie in diesem Fall zum Testergebnis. Wenn die Gleichheit fehlschlägt, wiederholen Sie (${ displaystyle a ^ {4d}}$ und so weiter) bis ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Wenn irgendwann nach dem Quadrieren einer anderen Zahl als ${ displaystyle pm 1}$ (mod n), du hast +1 (mod n), also ist n eine zusammengesetzte Zahl. Ob ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), dann ist n keine Primzahl.
   • Testergebnis: Wenn n den Test besteht, wiederholen Sie ihn für andere Werte eindas Vertrauen zu erhöhen.

Teil 2 von 3: Wie Einfachheitstests funktionieren

1. 1 Aufzählung von Teilern. Per Definition ist die Zahl n ist nur dann einfach, wenn sie nicht durch 2 und andere ganze Zahlen außer 1 und sich selbst teilbar ist. Mit der obigen Formel können Sie unnötige Schritte entfernen und Zeit sparen: Nachdem Sie beispielsweise überprüft haben, ob eine Zahl durch 3 teilbar ist, müssen Sie nicht überprüfen, ob sie durch 9 teilbar ist.
   • Die Funktion floor (x) rundet x auf die nächste ganze Zahl kleiner oder gleich x.
2. 2 Lernen Sie modulare Arithmetik kennen. Die Operation "x mod y" (mod ist eine Abkürzung des lateinischen Wortes "modulo", also "Modul") bedeutet "x durch y dividieren und den Rest finden". Mit anderen Worten, in der modularen Arithmetik wird beim Erreichen eines bestimmten Wertes, der als bezeichnet wird, Modul, "drehen" die Zahlen wieder auf Null. Zum Beispiel zählt die Uhr mit Modul 12 rückwärts: Sie zeigt 10, 11 und 12 Stunden an und kehrt dann zu 1 zurück.
   • Viele Rechner haben einen Mod-Key. Am Ende dieses Abschnitts erfahren Sie, wie Sie diese Funktion für große Zahlen manuell berechnen.
3. 3 Erfahren Sie mehr über die Fallstricke des Kleinen Satzes von Fermat. Alle Zahlen, für die die Testbedingungen nicht erfüllt sind, sind zusammengesetzt, der Rest jedoch nur wahrscheinlich sind einfach. Wenn Sie falsche Ergebnisse vermeiden möchten, suchen Sie nach n in der Liste der "Carmichael-Zahlen" (zusammengesetzte Zahlen, die diesen Test erfüllen) und "Fermat-Pseudoprimzahlen" (diese Zahlen erfüllen die Testbedingungen nur für einige Werte ein).
4. 4 Verwenden Sie bei Bedarf den Miller-Rabin-Test. Obwohl diese Methode für manuelle Berechnungen eher umständlich ist, wird sie häufig in Computerprogrammen verwendet. Es bietet eine akzeptable Geschwindigkeit und weniger Fehler als das Fermat-Verfahren. Eine zusammengesetzte Zahl wird nicht als Primzahl verwendet, wenn Berechnungen für mehr als ¼ Werte durchgeführt werden ein... Wenn Sie zufällig verschiedene Werte auswählen ein und für alle wird der Test ein positives Ergebnis liefern, wir können mit ziemlicher Sicherheit davon ausgehen, dass n ist eine Primzahl.
5. 5 Verwenden Sie für große Zahlen modulare Arithmetik. Wenn Sie keinen Mod-Rechner zur Hand haben oder der Rechner nicht für so große Zahlen ausgelegt ist, verwenden Sie Potenzeigenschaften und modulare Arithmetik, um die Berechnungen zu vereinfachen. Unten ist ein Beispiel für ${ Displaystil 3 ^ {50}}$ Mod 50:
   • Schreiben Sie den Ausdruck in eine bequemere Form: ${ Anzeigestil (3 ^ {25} * 3 ^ {25})}$ mod 50. Manuelle Berechnungen können weitere Vereinfachungen erfordern.
   • ${ Anzeigestil (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ Anzeigestil (3 ^ {25}}$ Mod 50 ${ Displaystil * 3 ^ {25}}$ mod 50) mod 50. Hier haben wir die Eigenschaft der modularen Multiplikation berücksichtigt.
   • ${ Displaystil 3 ^ {25}}$ Mod50 = 43.
   • ${ Anzeigestil (3 ^ {25}}$ Mod 50 ${ Displaystil * 3 ^ {25}}$ mod 50) mod 50 = ${ Anzeigestil (43 * 43)}$ Mod50.
   • ${ Anzeigestil = 1849}$ Mod50.
   • ${ Anzeigestil = 49}$.

Teil 3 von 3: Verwendung des chinesischen Restsatzes

1. 1 Wählen Sie zwei Zahlen. Eine der Zahlen muss zusammengesetzt sein und die andere muss der Einfachheit halber genau diejenige sein, die Sie testen möchten.
   • Zahl1 = 35
   • Zahl2 = 97
2. 2 Wählen Sie zwei Werte aus, die größer als Null bzw. kleiner als die Zahlen Number1 und Number2 sind. Diese Werte dürfen nicht gleich sein.
   • Wert1 = 1
   • Wert2 = 2
3. 3 Berechnen Sie den MMI (Mathematical Multiplicative Inverse) für Number1 und Number2.
   • Berechnen MMI
     • MMI1 = Nummer2 ^ -1 Mod Nummer1
     • MMI2 = Nummer1 ^ -1 Mod Nummer2
   • Nur für Primzahlen (dies ergibt eine Zahl für zusammengesetzte Zahlen, aber es ist nicht sein MMI):
     • MMI1 = (Zahl2 ^ (Zahl1-2))% Zahl1
     • MMI2 = (Zahl1 ^ (Zahl2-2))% Zahl2
   • Beispielsweise:
     • MMI1 = (97 ^ 33) % 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Erstellen Sie eine Tabelle für jedes MMI bis hinunter zu den log2-Modulen:
   • Für MMI1
     • F (1) = Zahl2% Zahl1 = 97% 35 = 27
     • F (2) = F (1) * F (1) % Zahl1 = 27 * 27 % 35 = 29
     • F (4) = F (2) * F (2) % Zahl1 = 29 * 29 % 35 = 1
     • F (8) = F (4) * F (4)% Zahl1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Zahl1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Zahl1 = 1 * 1% 35 = 1
   • Berechnen gepaarte Zahlen 1 - 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% Zahl2 = 35% 97 = 35
     • F (2) = F (1) * F (1) % Zahl2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2) % Zahl2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4) % Zahl2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8) % Zahl2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Zahl2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32) % Zahl2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Zahl2 = 35 * 35 mod 97 = 61
   • Berechnen Sie die gepaarte Zahl 2 - 2
     • 97 - 2 = 95 = (1011111) Basis 2
     • MMI2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = (((((35 * 35) % 97) * 61) % 97) * 35 % 97) * 61 % 97) * 35 % 97)
     • MMI2 = 61
5. 5 Berechnen (Wert1 * Zahl2 * MMI1 + Wert2 * Zahl1 * MMI2)% (Zahl1 * Zahl2)
   • Antwort = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Antwort = (2619 + 4270)% 3395
   • Antwort = 99
6. 6 Überprüfen Sie, dass Number1 keine Primzahl ist
   • Berechnen (Antwort - Wert1)% Zahl1
   • 99 – 1 % 35 = 28
   • Da 28 größer als 0 ist, ist 35 keine Primzahl.
7. 7 Überprüfen Sie, ob Number2 eine Primzahl ist.
   • Berechnen (Antwort - Wert2)% Zahl2
   • 99 – 2 % 97 = 0
   • Da 0 gleich 0 ist, ist 97 höchstwahrscheinlich eine Primzahl.
8. 8 Wiederholen Sie die Schritte 1 bis 7 mindestens noch zweimal.
   • Wenn Sie in Schritt 7 0 erhalten:
     • Verwenden Sie eine andere Number1, wenn Number1 keine Primzahl ist.
     • Verwenden Sie ein anderes Number1, wenn Number1 eine Primzahl ist. In diesem Fall sollten Sie in den Schritten 6 und 7 0 erhalten.
     • Verwenden Sie unterschiedliche Bedeutungen1 und Bedeutung2.
   • Wenn Sie in Schritt 7 durchgehend 0 erhalten, ist Nummer 2 sehr wahrscheinlich prim.
   • Die Schritte 1 bis 7 können zu einem Fehler führen, wenn Zahl1 keine Primzahl ist und Zahl2 ein Teiler von Zahl1 ist. Das beschriebene Verfahren funktioniert in allen Fällen, in denen beide Zahlen Primzahlen sind.
   • Der Grund, warum Sie die Schritte 1 bis 7 wiederholen müssen, liegt darin, dass Sie in einigen Fällen in Schritt 7 0 (für eine oder beide Zahlen) erhalten, selbst wenn Number1 und Number 2 keine Primzahlen sind. Dies geschieht selten.Wählen Sie eine andere Zahl1 (zusammengesetzt), und wenn Zahl2 keine Primzahl ist, ist Zahl2 in Schritt 7 nicht gleich Null (außer wenn Zahl1 ein Teiler von Zahl2 ist - hier sind Primzahlen in Schritt 7 immer gleich Null).

Tipps

• Primzahlen von 168 bis 1000: 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.
• Obwohl Brute-Force-Tests bei der Arbeit mit großen Zahlen ein mühsamer Test sind, ist er bei kleinen Zahlen recht effizient. Auch bei großen Zahlen sollten Sie zunächst kleine Teiler testen und dann zu komplexeren Methoden übergehen, um die Einfachheit von Zahlen zu überprüfen (wenn keine kleinen Teiler gefunden werden).

Was brauchst du

• Papier, Stift oder Computer