Die Community zu .NET und Classic VB.
Menü

Ist 643687241231983922... eine Primzahl?

 von 

Ist 64368724123198392222214792847837482347299873623498374898237427 eine Primzahl? 

Diese Frage kann man sich natürlich rein aus Interesse stellen. Mindestens genau so spannend ist aber ihre praktische Bedeutung, denn schließlich bilden Primzahlen das Kernstück der modernen Verschlüsselungstechnik. Wann immer wir zum Beispiel eine E-Mail verschlüsseln oder eine sichere Website über das https-Protokoll abrufen, sind im Hintergrund große Primzahlen im Spiel, und die müssen ersteinmal gefunden werden! Unser Problem bleibt jedenfalls: Wie kann ich entscheiden, ob eine riesige Zahl eine Primzahl ist oder zusammengesetzt?

Einleitung  

Wir haben auf ActiveVB nun bereits ein Tutorial Primzahlen-Algorithmus  [Tutorial 4001] , das ein direktes Rechenverfahren vorstellt und optimiert. Der Ansatz ist sehr plausibel:

Möchte ich prüfen, ob eine Zahl n eine zusammengesetzte Zahl ist, gehe ich alle möglichen Teiler dieser Zahl durch und prüfe, ob die Zahl von irgendeinem davon wirklich geteilt wird. Ist das nie der Fall, haben wir es mit einer Primzahl zu tun.

Man kann diesen Ansatz jetzt clever optimieren: Gerade Teiler kann ich sofort vergessen, sobald meine Zahl ungerade ist. Generell: Ist meine zu prüfende Zahl n durch eine andere Zahl nicht teilbar, so muss ich auf alle ihre Vielfachen gar nicht mehr prüfen und überspringe sie in der Suchfunktion. Und wenn ich ganz clever sein will, so muss ich nicht einmal alle Teiler bis n prüfen, sondern nur bis sqrt(n).

Das klingt nun schon recht effizient und Computer rechnen schnell, aber können wir das Ganze auf wirklich riesige Zahlen anwenden? Gut, was heißt riesig? Sagen wir 200 Stellen. Aber so weit müssen wir ja nicht prüfen, Wurzel draus, dann schonmal alle geraden Zahlen ignorieren, ... bleibt vielleicht eine 99-stellige Anzahl von möglichen Teilern zu prüfen. Mein PC schafft jetzt locker eine Million Teiler pro Sekunde, alles dauert also nur Zehn hoch 93 Sekunden. Moment, wie alt war noch das Universum? Vielleicht etwas mit Zehn hoch 19 Sekunden, schade.

Okay, natürlich könnten wir dieses oder ähnliche Verfahren noch weiter beschleunigen, indem wir geschickt viel mehr Zahlen ignorieren, aber wir laufen hier prinzipiell in eine Sackgasse. Man mag es kaum glauben, aber mit dem Algorithmus von oben beantworten wir eigentlich eine ganz andere Frage, als die, die wir wirklich lösen wollen. Die falsche Frage also. Ich modifiziere mal den Code aus dem Tutorial

Private Function prim(ByVal primzahl As Long) As String
    Dim j As Long
    For j = 3 To Sqr(primzahl - 1) Step 2
        If primzahl Mod j = 0 Then
            MsgBox CStr(primzahl) +  ist keine Primzahl, _
                   da " + CStr(j) + " sie teilt! ' <--
            Exit Function
        End If
    Next j
    prim = CStr(primzahl)
End Function

prim 527

Aha, "527 ist keine Primzahl, da 17 sie teilt", ist doch alles korrekt. Wir wissen nicht nur, dass die Zahl zusammengesetzt ist, sondern kennen auch gleich einen Faktor. Und damit wissen wir zu viel! Ursprünglich wollten wir wissen, "Ist n eine Primzahl?", die Frage die unser Algorithmus jetzt beantwortet ist aber "Finde mir einen Teiler von n". Ist das nicht dasselbe Problem? Nein! Das zweite Problem heißt Faktorisierungsproblem, und ist leider eines der härtesten Probleme, die die Informatik zu bieten hat. Es ist tatsächlich so hart, dass wir unsere geheimste Kommunikation dadurch sichern, dass es keiner lösen kann.

Auch unsere ursprüngliche Frage, ob eine Zahl nun prim ist oder nicht, ist schwierig, aber so schwierig wie das Faktorisierungsproblem ist sie nicht. Aber wie sollen wir wissen, dass eine Zahl nicht prim ist, ohne einen Faktor zu bestimmen?

In diesem Tutorial begeben wir uns auf die Suche nach "Belastungszeugen", mit denen wir eine Zahl überführen können, dass sie zusammengesetzt ist ohne sie zu faktorisieren. Die Lösung, die am Ende dabei herauskommt, ist verblüffend einfach und toll zu implementieren. Es ist auf den ersten Blick allerdings überhaupt nicht klar, warum das eigentlich funktioniert.

Im Folgenden möchte ich mich mit solcher Magie aber nicht zufrieden geben, sondern die Hintergründe entdecken, die sich hinter Primzahltests verbergen. Eine kleine mathematische Exkursion, in der wir uns so viel wie möglich von Grund auf selbst überlegen. Wer sich aber nur für das Ergebnis interessiert, kann natürlich auch einfach ans Ende scrollen.

Rechnen mit Mod  

Wenn wir unseren Belastungszeugen finden wollen, müssen wir uns zunächst nocheinmal mit einer Rechenoperation vertraut machen, die wir an sich schon kennen: Mod.

Den Modulo-Operator gibt es praktisch allen Programmiersprachen, er bestimmt den Rest der Division zwischen zwei Zahlen. Zum Beispiel liefert 17 Mod 5 das Ergebnis 2, denn es ist 17 : 5 = 3 Rest 2. Nützlich ist Mod zum Beispiel, um am Computer Teilbarkeit zu prüfen. Frage ich ab If a Mod 3 = 0 Then, dann prüfe ich, ob man a ohne Rest durch 3 teilen kann, also kurz, ob a durch 3 teilbar ist.

Es gibt aber auch viele alltägliche Beispiele, wo man im Kopf Mod rechnet. Zum Beispiel die Uhrzeit, alles Mod 12 oder Mod 24. Was ist 8 Stunden nach 21 Uhr? Naja eigentlich 29 Uhr, aber 24 Stunden sind ein voller Tag und uns interessiert ja nur der Rest, der nach letzter Mitternacht noch bleibt. Also 29 Mod 24 = 5 Uhr!

Vergessen wir einmal, dass es unendlich viele Zahlen gibt. Für den Moment lassen wir unser Universum nur aus den Zahlen 0 bis 23 bestehen und rechnen wie auf der Uhr! Das heißt, wir können normal rechnen, aber alle Zahlen und Ergebnisse werden am Schluss Mod 24 gerechnet. Wir dürften so die kluge Rechnung von oben festhalten als

21 + 8 = 29 = 5

Da sich diese Zeile unkommentiert aber recht komisch liest, schreiben wir in Klammern hinter die Gleichung, in welchem Universum wir das gerechnet haben.

21 + 8 = 29 = 5 (mod 24)

29 und 5 stellen im Weiteren aber wirklich dieselbe Zahl dar, man sagt, sie sind äquivalent. Ein paar mehr Gleichungen auf der Uhr

 1 +  1 =  2 (mod 24)
12 + 12 =  0 (mod 24)
 6 - 10 = 20 (mod 24)

Moment, Minus? Aber Zehn Stunden vor Sechs Uhr war 20 Uhr, alles richtig. Was ist mit den anderen Grundrechenarten? Nun, multiplizieren können wir auf der Uhr auch. Vier mal neun Stunden geschlafen und es ist

4 * 9 = 36 = 12 (mod 24) 

Stunden später (am Folgetag versteht sich). Das Schöne am Rechnen mit Mod ist jetzt, dass wir nicht alles stumpf zusammenrechnen müssen und auf das Mod 24 am Ende warten, sondern dass wir mit allen Rechenregeln an Ort und Stelle vereinfachen können wie bei normalen Termen. Zum Beispiel ist

  4 * 9 
= 4 * (6 + 3)
= 4 * 6 + 4 * 3 
= 24 + 12
= 0 + 12 
= 12 (mod 24)

eine absolut gültige (und sinnvolle) Umformung. Auch größere Terme schnell auszurechnen ist so überhaupt kein Problem. Probieren wir einmal etwas Neues: Wir rechnen (mod 7), es geht also um, richtig, Wochentage! Wir nummerieren uns gedanklich die Woche durch, sagen wir z.B. Sonntag sei Tag 0, Montag Tag 1, usw.. Fünfzehn Tage nach Montag ist dann Dienstag, denn

1 + 15 = 1 + 1 = 2 (mod 7)

Okay, Prinzip klar? 2012 ist Weihnachten an einem Montag, an welchem Tag war es vor 10 Jahren? Heißt, 10 mal 365 Tage zurück und noch drei Schalttage, wir wollen also

1 - (10*365 + 3) = ?? (mod 7)

im Kopf bestimmen. Natürlich ist 10 = 3 (mod 7), und die 365? Da vereinfachen wir

365 = 350   + 15
    = 7*50  + 15
    = 0*50  + 1
    = 1 (mod 7)

Also ist unser Ergebnis

1 - (3*1 + 3) = 1 - 6 = 2 (mod 7),

Weihnachten war an einem Dienstag.

Was hat das nun alles mit unserer Suche nach Primzahlen zu tun? Noch konnten wir im (mod 24) und im (mod 7)-Universum auf die genau gleiche Art rechnen. Bald werden wir aber sehen, dass bei (mod 24) verdächtige Dinge passieren, die es bei (mod 7) nicht gibt. Solche, mit denen man eine Zahl überführen kann, dass sie zusammengesetzt ist. Um diesen Unterschied im Worte zu fassen müssen wir zuerst noch eine einfache mathematische Struktur kennen lernen.

Ein bisschen Gruppentheorie  

Stellen wir uns einmal die Menge aller positiven rellen Zahlen vor. Mit denen kann man jetzt alles Mögliche machen, aber für den Moment konzentrieren wir uns nur darauf, was Malnehmen eigentlich bedeutet. Dann können wir vier einfache Feststellungen treffen:

  1. Sind a und b positive Zahlen, dann ist a*b wieder eine positive Zahl. Logisch.
  2. Sind a, b, c positive Zahlen, dann ist (a*b)*c=a*(b*c), Klammern sind also egal
  3. Es gibt eine spezielle positive Zahl 1, so dass 1*a = a*1 = a für jede andere positive Zahl a
  4. Ist a eine positive Zahl, dann gibt es eine Zahl b, so dass a*b = b*a = 1. Klar, b ist der Kehrwert von a.

Klingt offensichtlich, was hilft uns das? Nun gut, dann stellen wir und jetzt einmal eine ganz andere Menge vor: Die Menge aller geometrischen Drehungen im Koordinatensystem um den Ursprung. Außerdem vereinbaren wir Folgendes:

Ist a eine Drehung und b eine Drehung, dann schreiben wir a*b für die Drehung, die erst mit a dreht und dann mit b.

Zum Beispiel könnten wir schreiben

(Drehung um 10°) * (Drehung um 60°) = (Drehung um 70°)

Mit dieser Definition gibt's wieder Feststellungen

  1. Sind a, b Drehungen, dann ist a*b wieder eine Drehung. Logisch, das haben wir so definiert.
  2. Sind a, b, c Drehungen, dann ist (a*b)*c=a*(b*c). Klar, was zuerst passiert ist egal.
  3. Bezeichnen wir mit e die Drehung um 0°. Dann ist e*a=a*e=a für jede andere Drehung a. Die Drehung um 0° lässt ja alles, wie es ist.
  4. Ist a eine Drehung, dann gibt es eine Drehung b so dass a*b=b*a=e. b ist hier die entgegengesetzte Drehung zu a.

Moment, diese Feststellungen hatten wir doch schonmal! Offenbar funktionieren Drehen und Zahlen multiplizieren auf die gleiche Weise, obwohl es ganz verschiedene Dinge sind. Mathematiker finden so eine Verbindung spannend genug, um sich zu fragen, über welche Objekte sich noch dieselben Feststellung treffen lassen. Alles, was das hergibt, darf sich in der Fachsprache eine Gruppe nennen. Ein Mathematiker würde uns also die Absätze oben zusammenfassen durch

Die positiven reellen Zahlen bilden mit der Multiplikation als Verknüpfung eine Gruppe.
Die Drehungen um den Ursprung bilden mit der Hintereinander-Ausführung eine Gruppe.

Heute kennt man Unmengen von Dingen, die eine Gruppenstruktur haben. Mal ein paar Beispiele, der Leser kann gerne schnell checken, dass sich die Feststellungen 1 bis 4 überall wie oben treffen lassen.

  • Reelle Zahlen ohne die Null mit *
  • Ganze Zahlen mit +
  • {True,False} mit XOR

aber auch

  • Die Vertauschungen (Permutationen) von Elementen mit Hintereinander-Vertauschung
  • Die Drehungen beim Rubik's Cube mit Hintereinander-Drehung

Das ist ja alles schön und gut festzustellen, aber was hilft es uns, Dinge in eine abstrakte Struktur einzusortieren? Nichts, wenn nicht die Theorie von dem, was man über Gruppen sagen kann, von klugen Menschen seit Jahrhunderten erforscht worden wäre. Wenn ich also irgendwie zeigen kann, dass mein Problem etwas mit Gruppen zu tun hat, dann kann ich sofort das geballte Wissen der Gruppentheorie darauf werfen und für meine Lösung benutzen. Und glücklicherweise ist die Gruppenstruktur genau das, was wir brauchen, um Prim- und zusammengesetzte Zahlen zu unterscheiden.

Einen mathematischen Satz beweisen  

Die Idee ist folgende: Wir haben bis jetzt gelernt Modulo zu rechnen und ahnen, dass irgendwo in der Gruppentheorie die Lösung unseres Problemes liegt. Was wir jetzt brauchen, ist eine Brücke zwischen den beiden vorangegangenen Abschnitten: Eine kleine mathematische Aussage, die wir aber diesmal nicht einfach glauben, sondern uns Stück für Stück selbst beweisen.

Sei p eine natürliche Zahl. Dann bilden die Zahlen {1, 2, ..., p-1} mit der Multiplikation (mod p) genau dann eine Gruppe, wenn p eine Primzahl ist.

Wenn das wahr ist, dann dürfen wir uns ja eine beliebige Primzahl p festhalten und die Zahlen 1,..,p-1 müssen die vier Feststellungen über eine Gruppe mitmachen. Das versuchen wir einmal zun zeigen. Am einfachsten sind die Feststellungen 2 und 3, also beginnen wir mit diesen. Damit wir im Übrigen nicht ständig {1, ..., p-1} schreiben müssen, kürzen wir das mit [p] ab. Also los geht's:

II. Es gilt (a*b)*c = a*(b*c) (mod p). Das wissen wir schon, einfach Rechenregeln!

III. Es gibt ein Element 1, für das gilt 1*a = a*1 = a (mod p). Ja, die 1 eben, und die ist in der Menge [p] auch enthalten.

Nun geht es an die erste Feststellung über Gruppen:

I. Behauptung: Sind a, b in [p], dann liegt a*b Mod p in [p].

Das braucht einen kleinen Beweis: Durch das Mod p wissen wir schoneinmal, dass das Ergebnis zwischen 0 und p-1 liegt. Es könnte aber passieren, dass das Ergebnis 0 beträgt. In dem Fall würde die Behauptung aber nicht erfüllt, da die 0 nicht in [p] liegt! Wir können aber durch einen Widerspruchsbeweis zeigen, dass nie die 0 herauskommt.

Das heißt wir nehmen theoretisch einmal an, es gäbe solche a, b in [p], so dass a*b Mod p = 0 rauskommt. Das heißt, ab lässt sich ohne Rest durch p teilen. Da p eine Primzahl ist, geht das nur, wenn p irgendwo in der Primfaktorzerlegung von ab vorkommt. Das heißt entweder a oder b müsste schon ein Vielfaches von p gewesen sein. Das ist aber unmöglich, weil sie beide je nur höchstens p-1 betragen. Also ist es unmöglich, dass bei dem Produkt 0 herauskommt! Damit ist unsere Behauptung gerettet.

Okay, drei Punkte haben wir schon, das ist mindestens eine Halb-Gruppe. Für eine echte Gruppe brauchen wir aber noch den vierten Punkt, der ein bisschen länger wird.

IV. Behauptung: Ist a in [p], dann gibt es ein b in [p] so dass a*b = 1 (mod p). Hmm, das klingt ja wunderlich, man nimmt ganze Zahlen mal und bekommt 1 heraus? Primzahlen machen's möglich!

Probieren wir's doch einmal aus, für (mod 5) zum Beispiel:

1 * 1 = 1 (mod 5)
2 * 3 = 1 (mod 5)
3 * 2 = 1 (mod 5)
4 * 4 = 1 (mod 5) 

Hey, funktioniert ja wirklich. Und wie ist das bei (mod 7)? Gehen wir einmal systematisch heran und suchen die Zahl x, so dass 3*x = 1 (mod 7). Dazu multiplizieren wir einfach mal der Reihe nach alle Zahlen von 1,..,6 mit 3 durch.

3 * 1 = 3 (mod 7)
3 * 2 = 6 (mod 7)
3 * 3 = 2 (mod 7)
3 * 4 = 5 (mod 7)
3 * 5 = 1 (mod 7)
3 * 6 = 4 (mod 7)

Siehe da, 3 * 5 = 1 (mod 7) wie wir wollten, aber wir sehen noch mehr: Wir haben nie zwei gleiche Zahlen in den Produkten herausbekommen. Wenn es aber keine Zahl doppelt trifft, muss umgekehrt jede Zahl einmal getroffen werden, also auch die 1. Vielleicht ist das immer so?! Versuchen wir wieder mit einem Widerspruch zu zeigen, dass für eine Zahl a und unterschiedliche Zahlen x und y immer gilt

a*x <> a*y (mod p)

Na gut, nehmen wir das theoretische Gegenteil an: Man könnte es mit irgendwelchen Zahlen x,y hinkriegen, dass

a*x = a*y (mod p).

Dann stellen wir um und klammern aus

a*x - a*y = 0 (mod p)
=> a*(x-y) = 0 (mod p)

Aha, so eine Gleichung haben wir schonmal gesehen. Da x und y verschieden sind, ist x - y nicht 0. Mit demselben Argument wie aus Feststellung 1 sehen wir, dass aus so einem Produkt dann nie 0 herauskommen kann, da ist unser Widerspruch. Die Produkte von a und den Zahlen 1, ..., p-1 müssen also wirklich alle verschieden sein und wir bekommen damit an irgendeiner Stelle die 1 heraus! Voilà, alles ist gezeigt, was wir für eine Gruppe brauchen.

Und was, wenn p keine Primzahl ist? Wieso kann {1, ..., 5} keine Gruppe (mod 6) sein? Ich sage nur

2 * 3 = 0 (mod 6)

Das widerspricht doch glatt der ersten Feststellung, die 0 wollen wir nicht in unserer Struktur drinhaben. Genau dasselbe Argument zieht für jede zusammengesetzte Zahl, wir können überall einen sog. Nullteiler provozieren. Und die gibt es in Gruppen nicht.

Der Fermat-Test  

Okay, der schwierige Teil wäre geschafft und wir haben jetzt endlich ein Kriterium entdeckt, mit dem wir Prim- und zusammengesetzte Zahlen unterscheiden können. Nämlich: Ist p eine Primzahl, dann müssen die Zahlen 1, ..., p-1 alles mitmachen, was die Gruppentheorie über sie sagt, ist p zusammengesetzt, bilden sie keine Gruppe und haben folglich überhaupt keinen Grund dazu!

Natürlich könnte es passieren, dass sie trotzdem durch Zufall bei der ein- oder anderen Eigenschaft mitmachen. Solche Zahlen nennt man Lügner oder Pseudoprimzahlen. Aber was Test a mitmacht muss nicht auch bei Test b Glück haben. Durch die richtige Auswahl von Tests kriegt man die Wahrscheinlichkeit, eine Pseudoprimzahl zu finden, verschwindend gering.

Fehlt nur noch eine Gruppeneigenschaft, die wir bequem testen können. Ein schöner Satz aus der Gruppentheorie ist der Satz von Lagrange. Zur Schreibweise: Wenn G irgendeine Gruppe mit ihrer Operation * ist, dann können wir auch Potenzen eines Elements erklären, indem wir es mehrmals hintereinander multiplizieren wie bei normalen Zahlen auch. Also

a^2 = a*a
a^3 = a*a*a
a^4 = a*a*a*a
a^n = ...

Der Satz von Lagrange erlaubt nun diese interessante Aussage

Wenn G eine endliche Gruppe mit n Elementen ist, dann gilt für jedes a aus G, dass a^n = 1.

Das gilt wirklich für jede endliche Gruppe und lässt sich nur aus den vier Gruppeneigenschaften herleiten, ganz egal um welche Objekte sich dabei konkret handelt. Heißt für uns: Unsere Menge {1, ..., p-1} hat p-1 Elemente, folglich muss für jede Zahl a daraus gelten, dass

a^(p-1) = 1 (mod p).

Das sieht ja nach einer einfachen Bedingung aus! Wenn p eine Primzahl ist, dann muss diese Gleichung laut Gruppentheorie gelten, wenn es keine ist, wird sie es wahrscheinlich nicht. Und was ist a? Naja, jede beliebige Zahl aus der Gruppe muss das mitmachen, d.h. wir können mit 2 anfangen.

Die Aussage oben ist bekannt als der kleine Satz von Fermat und wir haben ihn hiermit bewiesen. Den Primzahltest, den wir damit geschenkt kriegen, nennt man daher auch den Fermat-Test .

Die Implementierung

Ist es wirklich so einfach? Probieren wir es aus. 5 ist eine Primzahl, also setzen wir p=5 uns prüfen aufs Geratewohl a=2. Dann müsste ja gelten

2^(5-1) = 1 (mod 5)

Aber siehe da, das ist ja

2^4 = 16 = 1 (mod 5)

Stimmt! Und wie ist das für eine zusammengesetzte Zahl? Nehmen wir z.B. p=6 und prüfen die Bedingung:

2^(6-1) = 2^5 = 32 = 2 (mod 6)

Ist eine keine 1 herausgekommen. Damit ist zweifelsfrei bewiesen, dass die 6 keine Primzahl ist, ohne dass wir einen Teiler bestimmen mussten.

Bleibt nur die Frage ob dieser Test wirklich effizient durchzuführen ist. Wir machen uns schoneinmal keine Sisyphos-Arbeit mit einer Faktorisierung aber immerhin müssen wir Zwei hoch eine riesige Zahl bestimmen, wie soll das praktikabel sein? Aber glücklicherweise interessiert uns auch diese Potenz ja nicht, sondern wieder nur der Rest einer Division am Ende, das Mod p.

In diesem Beispiel berechnen wir also nocheinmal eine größere Potenz und machen den Fermat-Test für die Zahl 257.

Wenn wir naiv die Potenz ausrechnen, kriegen wir folgende Aussage

2^256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936
      = 1 (mod 257)

Offenbar besteht die 257 den Test, wie sie es soll, aber angenehm ist die Rechnung nicht. Geschickter rechnen wir mit kleinen Zwischenschritten:

2^2  = 4 (mod 257)
2^4  = (2^2)^2 = 4^2   = 8            (mod 257)
2^8  = (2^4)^2 = 8^2   = 64           (mod 257)
2^16 = (2^8)^2 = 64^2  = 4096  = 241  (mod 257)
2^32 =     ... = 241^2 = 58081 = 256  (mod 257)
2^64 =     ... = 256^2 = 65536 = 1    (mod 257)
...
2^256 = (2^64)^4 = 1^4         = 1    (mod 257)

Das sind jetzt gar keine großen Zahlen mehr, man hätte das zur Not sogar von Hand noch hingekriegt. Mit vergleichsweise wenigen Schritten kann man nach einem ähnlichen Prinzip beliebige, riesige Potenzen (mod p) ausrechnen. Der Fermat-Test ist damit tatsächlich praktikabel.

Um ihn endlich für "interessante" Größen auszuprobieren, benötigen wir höchstens noch eine Klasse, die in der Lage ist, so große Zahlen überhaupt zu repräsentieren. Unter .NET (wie mittlerweile in den meisten Sprachen) gibt es so eine Klasse bereits. Hier heißt sie BigInteger und wir binden sie mit dem Verweis auf System.Numerics ein. Die beschleunigte Berechnung der Modulo-Exponentialfunktion, wie wir sie oben benutzt haben, ist ebenfalls ein Klassiker und wird uns fertig angeboten, hier als ModPow (oft heißt diese Funktion PowerMod).

Damit sind wir endlich so weit, die Frage vom Anfang des Tutorials zu beantworten.

Dim num = "64368724123198392222214792847837482347299873623498374898237427"
Console.WriteLine(FermatTest(num))

Function FermatTest(number As String) As BigInteger
    Dim p = BigInteger.Parse(number)

    Return BigInteger.ModPow(2, p - 1, p)
End Function

Unsere Antwort?

26940057434618495167977936204540455109325640842252048822999269

Wäre unsere Zahl eine Primzahl gewesen, egal wie groß, wäre die Antwort

1

gewesen. So ist es keine. Und was ihre Teiler sind? Niemand wird es wissen! Um unsere Methode am Ende noch sicherer zu machen, verlassen wir uns nicht nur auf die Basis 2, sondern probieren einfach ein paar zufällige Basen aus. Schlägt einer der Tests fehl, haben wir die zusammengesetzte Zahl ja bereits überführt. Hier haben wir also unsere endgültige Version des Primzahltests

Function IsFermatPrime(number As String, n As Integer) As Boolean
    Dim p = BigInteger.Parse(number), len = number.Length

    If p = 2 Then Return True
    If p.IsEven Then Return False

    ' n Test-Durchläufe
    For j = 1 To n

        ' Geeignete zufällige Basis suchen
        Dim a As BigInteger
        Do
            a = RandomBigInt(len, True)
        Loop Until (a > 1) And (a < p)

        ' Können wir die Zahl überführen?
        Dim res = BigInteger.ModPow(2, p - 1, p)
        If res <> 1 Then Return False
    Next

    Return True
End Function

Function RandomBigInt(numDigits As Integer, Optional randomLength As Boolean = False) As BigInteger
    Static rnd As New Random()

    If randomLength Then numDigits = rnd.Next(1, numDigits + 1)

    Dim num = String.Join("", (From i In Enumerable.Range(1, numDigits) Select res = rnd.Next(0, 10).ToString()).ToArray())

    Return BigInteger.Parse(num)
End Function

Ausblick  

Der Fermat-Test ist implementiert und damit sind wir ganz gut aufgestellt. Wie können wir damit jetzt große Primzahlen generieren?

Dim p As BigInteger, j As Integer
Do
    p = RandomBigInt(150)
    j = j + 1
Loop Until IsFermatPrime(p.ToString(), 3)

Console.WriteLine("Habe Primzahl {0} nach {1} Durchläufen gefunden", p, j)

Einfach das, Durchprobieren! Natürlich kann man sich da wieder cleverer anstellen (vorsortieren, die Zahl der Tests variieren), aber so blöde wie es scheint ist die Brute-Force-Methode gar nicht. Man kann zwar wenig über die genaue Verteilung von Primzahlen in einem Intervall aussagen, aber dass irgendwo welche - und ausreichend viele - vorkommen ist so gut wie gesichert. Und so findet der Algorithmus nach vielleicht tausend Kandidaten endlich seine Primzahl.

Das soll aber nicht heißen, dass das damit letzte Wort in Sachen Primzahltests gesprochen sei. Zum Abschluss lasse ich daher einfach mal folgendes Codeschnipsel und das Stichwort Carmichael-Zahl stehen

Dim n = 3 * 11 * 17
Console.WriteLine(IsFermatPrime(n.ToString(), 100))

Ihre Meinung  

Falls Sie Fragen zu diesem Artikel haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.

Danke! :) - sauternic 20.05.18 02:28 2 Antworten