Probabilistisch. Ist das nicht ein tolles Wort? Aus diesem Grund habe ich heute was in Haskell programmiert. Das und weil ich Haskell lernen muss. In der Vorlesung „Diskrete Strukturen“ ging es heute um Anwendungen (der Prof musste seinen Inhalt mal legitimieren…) der Dinge die man da so lernt. Eines davon ist der kleine Satz von Fermat der im wesentlichen aussagt, dass wenn man eine Zahl a mit einer beliebigen Primzahl potenziert und dann modulo der Zahl teilt ( man dividiert und das Ergebnis ist der Rest. Bsp. 5 modulo 2 ist 1, denn 2*2 +1 = 5), wieder a bekommt. Das ganze leicht abgewandelt ergibt einen Test, ob eine Zahl eine Primzahl ist:

[latex]a^{p-1}\equiv 1~(mod~p)[/latex]

Ein kleines Problem gibt es allerdings. Es gibt auch Zahlen, die diesen Test erfüllen und trotzdem keine Primzahlen sind. (Carmichael-Zahlen) auch andere Zahlen liefern für bestimmtes a ein wahres Ergebnis, aber für andere nicht.

So viel zur Vorrede. Ich hab das ganze mal in Haskell implementiert und muss sagen: nicht schlecht. 4 Zeilen Code ist schon sportlich.

[gist id=4340052]

Ich muss da sagen, dass diese Implementation nicht sehr gut ist. Ist die Zahl eine Primzahl ist das Programm sehr schnell. Wenn nicht, müssen alle a durchgerechnet werden ( und das sind x-1 viele) und erst wenn die liste dann leer bleibt wird false zurückgegeben. Das lässt sich sicher richtig machen, aber ich übe ja noch :-)

Das ganze wird natürlich keinem nützen, aber ich fand es toll mal anzuwenden, was in der Vorlesung behandelt wird. Genauso wie ich mich gefreut habe, als wir in Analysis ein Programm schreiben sollten, dass die Quadratwurzel für gegebenes a errechnet. Sehr toll