AuK/Probabilistische Algorithmen SS11
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
Autoren:
* [mailto:s3makuba@stud.hs-zigr.de Martin Kubasch]
* [mailto:s3frtesk@stud.hs-zigr.de Fred Teske]
==Einleitung==
Probabilistische Algorithmen werden auch randomisierte oder stochastische Algorithmen genannt. Das Ergebnis dieser Art von Algorithmen ist vom Zufall abhängig. Sie bringen oft eine Effiziensverbesserung mit sich, da Entscheidungsfragen zufällig beantwortet werden, bei denen die Zeit zur Berechnung des korrekten Resultates untragbar lang wäre. Probabilistische Algorithmen können sich, mehrfach auf ein und dasselbe Problem angewandt, unterschiedlich verhalten. Die Ausführungszeiten und die Ergebnisse können teilweise deutlich voneinander abweichen.
Um probabilistische Algorithmen zu erstellen werden Zufallszahlen benötigt. Diese werden mit Hilfe von Generatoren erstellt.
==Pseudozufallszahlen==
Definition von Zufallszahlen:
Spricht man von Zufallszahlen so meint man in diesen Sinne eine Zahl die man nicht vorhersehen kann und die keinem Bildungsgesetz unterliegt. Im Duden findet man daher auch folgende Definition: Eine Zahl, die rein statistisch(zufällig) aus einer Menge von Zahlen herausgegriffen wird. Eine (unendliche) Folge von Zahlen ohne (algorithmisches) Bildungsgesetz heißt Zufallszahlenfolge.
Als kleines Beispiel dafür kann man eine Münze als sehr einfachen Zufallsgenerator sehen der entweder Kopf = 1 oder Zahl = 0 ausgibt.
[[Bild:S3makuba_Münzen.jpg]]
20 Münzwürfe hintereinander:
(1) <math> 1.1.1.1.1.1.0.0.1.0.0.1.1.0.0.0.0.1.1.0 </math> hierbei ist kein Bildungsgesetz zu erkennen
Somit hat man eine Reihe von "echten Zufallszahlen" erschaffen.
Im Gegensatz zur echten Zufallszahlen sind Pseudozufallszahlen deterministisch erzeugte Zahlen die den Anschein erwecken sollen sie seien rein zufällig gewählt worden. Da in einem deterministischen Algorithmus jeder Schritt fest bestimmt ist, kann die Zahl von vornherein bestimmt werden und ist somit nicht zufällig.
Bei probabilistischen Algorithmen spielen Zufallszahlen eine besondere Rolle. Höhere Programmiersprachen verfügen über Sprachelemente für Zufallszahlen. In Java gibt es beispielsweise die Klasse Random. Es wird eine natürliche Zahl <math>n</math> als Argument erwartet. Die Ausgabe ist eine natürliche Zahl <math>r</math> mit <math>0 \le r < n</math>. Die Transformation in ein abgeschlossenes Intervall <math>[a,b]</math> natürlicher Zahlen lässt sich leicht bewerkstelligen. Wie folgendes Beispiel zeigt.
<code id="4dcbf4b7d024f">
public static int intervall(int a, int b){
Random randomGenerator = new Random();
return (a + randomGenerator.nextInt((b - a) + 1));
}
</code>
<run id="4dcbf672ced17">intervall(1, 7);</run>
Die Erzeugnung von Zahlen nach obigen Beispiel erfolgt jedoch nicht rein zufällig. Sie werden deterministisch berechnet d.h. es gibt Prozeduren, die in der Lage sind, lange Folgen von Werten zu generieren, die scheinbar die Eigenschaften zufälliger Folgen haben.
Ein Verfahren zum Erzeugen von Zufallszahlen ist die Kongruenzmethode, die 1948 von D. H. Lehmer entwickelt wurde. Ausgehend von einem Startwert, dem sogenannten Seed wird folgende rekursive Vorschrift angewand.
<math>z_{n} = (a * z_{n-1} + b)</math> <math>mod</math> <math>c</math>
dabei sind
*<math>a</math> ein Multiplikator, der eine möglichst große Primzahl sein sollte
*<math>b</math> eine Konstante (im Fall von <math>c = 0</math> spricht man von multiplikativer Kongruenz)
*<math>c</math> ist das Argument der Modulo Funktion und sollte möglichst einen hohen Wert besitzen, da es die Länge der Zahlenfolge angibt
Dabei ist zu beachten, dass der selbe Seed immer die selbe Zahlenfolge liefert. Um unterschiedliche Folgen zu erhalten ist es notwendig unterschieliche Seeds zu wählen. Oftmals wird der Seed in Abhängigkeit der Systemzeit gewält.
==Numerische probabilistische Algorithmen==
Algorithmen dieser Art produzieren eine Näherungslösung mit wählbarer Genauigkeit.
Ein Beispiel für diese Klasse von Algorithmen ist die Bestimmung einer Näherung für die Zahl <math>\pi</math> durch "Zufallsregen". Dabei werden <math>n</math> Regentropfen auf eine quadratische Fläche fallen gelassen, in der sich ein Kreis befindet. Anschließend werden die Regentropfen gezählt, die innerhalb des Kreises gefallen sind.
Es wird angenommen, dass jeder Punkt im Quadrat exakt dieselbe Wahrscheinlichkeit hat, von einem Tropfen getroffen zu werden.
Ist der Radius des Kreises <math>r</math>, so ist seine Fläche <math>\pi r^2</math>, wobei die Fläche des Quadrats <math>4r^2</math> ist. Somit ist der durchschnittliche Anteil der Tropfen, die innerhalb des Kreises landen, <math>\frac{\pi r^2}{4r^2} = \frac{\pi}{4}</math>. Damit kann <math>\pi</math> mit <math>\pi \approx \frac{4 k} {n}</math> geschätzt werden.
<div align="center"><video type=youtube>EbC0eP0Dq9A&NR</video></div align="center">
Codebeispiel eines Algorithmus, der mit "Zufallsregen" arbeitet. Je höher <math>n</math> gewählt wird umso genauer lässt sich <math>\pi</math> abschätzen.
<code id="4de2a4b849649">double rain(int n){
int k = 0;
for(int i = 0; i < n; i++){
double x = Math.random();
double y = Math.random();
if(x*x + y*y <= 1){
k = k+ 1;
}
}
double pi = new Double (4) *k/n;
return pi;
}</code>
<run id="4dc540a538d1c">rain(100);</run>
Ein weiteres bekanntes Beispiel für diese Klasse von Algorithmen, die "Zufallsregen" verwenden ist die [http://de.wikipedia.org/wiki/Numerische_Integration numerische Integration].
==Las Vegas Algorithmus==
===Grundlage===
Ein solcher Algorithmus (randomisierter Algorithmus) folgt dem einfachen Prinzip immer ein richtiges Ergebnis auszugeben. So erklärt sich der Name des Las Vegas Algorithmus aus der Tatsache das Casinos immer gewinnen (bezogen auf ein korrektes Ergebnis). Es kann jedoch der Fall eintreten das die Zufallssteuerungen in Sackgassen (nicht zulässige Ergebnissen) landen. In diesen Fall gibt es kein Ergebnis. Durch mehrfaches Ausführen des Algorithmuses kann jedoch ein richtiges Ergebnis gefunden werden.
'''Beispiel:'''
Das n-Damen Problem ist eines der bekanntesten in der Mathematik und besteht darin auf einen Schachbrett mit n*n Feldern eine Anzahl von n Damen so zu verteilen das sich niemals zwei Damen schlagen können. In der Informatik wurde dieses Problem auf mehrere Arten gelöst wie beispielsweise mit Backtracking. Dieses Problem kann man jedoch auch mithilfe der probabilistischen Algorithmen lösen.
[[Bild:S3makuba_Image349nk.gif]]
Lösung des Problems mit Las Vegas Algorithmen (Pseudocode):
'''''1.for i = 1 to n:'''''
'''''Wenn in Reihe i alle Felder bedroht sind, Abbruch.'''''
'''''Anderenfalls wähle zufällig eines der nicht bedrohten Felder.'''''
'''''2.Wiederhole (1), bis eine Lösung gefunden ist.'''''
Dieser Algorithmus terminiert nicht immer. Wird aber eine Lösung gefunden ist diese mit Wahrscheinlichkeit 1 richtig.
===Analyse des Aufwands:===
Gehen wir davon aus es gibt einen Las Vegas Algorithmus <math>LV(x)</math> der eine Eingabe <math>x</math> nimmt und als Ausgabe ein Scheme-paar <math>(y , Erfolg )</math> gibt.
Dabei kann Erfolg entweder <math>true</math> "Ergebnis wird gefunden", oder <math>false</math> "Berechnung landet in Sackgasse" und gibt nach (vorher vereinbarten) Anzahl von erfolglosen versuchen <math>false</math> aus. Das <math>y</math> ist der Wert der bei der erfolgreichen Suche rauskommt.
Um nun eine Aufwandsanalyse durchzuführen, benötigt man eine Prozedur (<math>LV-loop</math>) bei der <math>LV(x)</math> solange ausgeführt wird bis ein Ergebnis herauskommt(hartnäckiger Algorithmus).
Code:
(define LV-loop
(lambda (x)
(let* ((resultat (LV x))
(y(car resultat))
(Erfolg (cdr resultat)))
(if Erfolg
y
(LV-loop)))))
Im Fall der Las Vegas Algorithmen muss man von der Möglichkeit ausgehen das eine Anzahl n von Versuchen benötigt wird um ein richtiges Ergebnis auszugeben. Um nun den Zeitaufwand t(x) zu berechnen, brach man die Variablen <math>success(x)</math> im Fall des erfolgreichen Findens eines Ausgabewertes und <math>failure(x)</math> im Fall keines erfolgreichen Ergebnisses. Des weiteren muss noch die Zeit eingerechnet werden, die gebraucht wird um aus einer Sackgasse wieder raus zukommen, bezeichnet mit der Variable <math>p(x)</math>. Man geht bei <math>p(x)</math> von <math>0 < p(x) < 1</math> aus.
'''
Gleichung:'''
<math>t(x)=p(x) \cdot success(x)+(1-p(x)) \cdot (failure(x)+t(x))</math>
<math>t(x) = success(x) + (1- p(x)) / p(x) * failure(x)</math>
<math>t(x)=success(x)+ \left( \frac{1}{p(x)} - 1 \right) \cdot failure(x)</math>
'''Beispiel:
'''
<math> success(x) = 10</math>
<math> failure(x) = 13</math>
<math> p(x) = 0,25</math>
<math> t(x) = 10 + ((1/ 0,25) - 1) * 13 </math>
<math> t(x) = 10 + ( 4 - 1 ) * 13 = 49</math>
===Sherwood-Algorithmen===
Sherwood-Algorithmen sind eine Spezielle Form der Las-Vegas Algorithmen ,welche immer ein richtiges Ergebnis ausgeben. Das Bedeute es gibt keine Berechnungen die in Sackgassen führen. Sherwood-Algorithmen sind deterministisch (das bedeutet das determinstische Algorithmen zu probabilistischen Algorithmen umgeformt werden).
Dieser Algorithmus wird besonders gern bei Problemen mit großer Aufwandsdifferenz zwischen den best- ,average-, und worst-case genutzt ,da er die besonder Eigenschaft besitzt die großen Aufwandsdifferenzen so "abzufedern" das immer ein Mittlerer Aufwand entsteht.Das bedeutet zwar nicht das der best-case oder der worst-case völlig ausgeschlossen sind,jedoch sind diese durch den zufälligen Faktor sehr unwahrscheinlich. Diese Negation der Aufwandsdifferenz wird auch als "Robin Hood Effekt" bezeichnet, da dieser von den reichen nahm und den armen gab (in diesen Fall so gedeutet das von den hohen Aufwand genommen wurde und dem niedrigen Aufwand gegeben wurde)und sich somit die Aufwandsdifferenz aufhebt.
Daher kommt auch der Name der Sherwood-Algorithmen ,da Robin Hood im Sherwood Forrest lebte.
'''Beispiel:'''
Ein Beispiel für die Nutzung der Sherwood-Algorithmen ist ein "randomisiertes" Quicksort.
Das ist in dem Sinne zu verstehen, das beim Quicksort der Fall des Worst case eintreten kann und somit eine Zeitkomplexität von <math>O(n^2)</math> entsteht.
Um dies zu verhindern gibt es zwei Möglichkeiten. Entweder man bringt die zu ordnenden Elemente "durcheinander" ,was bedeutet das unsortiertere Listen besser zu ordnen sind als sortierte. Es gibt aber auch die Möglichkeit das Pivotelement "zufällig" auswählen zulassen indem man bei der Programmierung immer das Zufallselement für die bestimmung vom Pivotelement nimmt.So kann man mit hoher Sicherheit (aber nicht vollkommen) davon ausgehen das immer eine Zeitkomplexität von <math>O(n*(log(n))</math> besteht.
==Monte-Carlo-Algorithmen==
Algorithmen dieser Art geben mit hoher Wahrscheinlichkeit das korrekte Ergebnis aus. Können sich jedoch gelegentlich irren. Irren bedeutet hier das Ergebnis ist falsch und nicht "knapp daneben". Im Falle eines Fehlers liefert der Algorithmus ülicherweise keine Warnung. Dies nimmt man jedoch in Kauf um Probleme zu lösen, die sonst nur schwer oder in keiner angemessenen Zeit gelöst werden könnten.
Ein Monte-Carlo-Algorithmus wird ''p-korrekt'' genannt, wenn er eine richtige Lösung mit einer Wahrscheinlichkeit nicht kleiner als <math>p</math> liefer. Dabei ist <math>p</math> eine reele Zahl mit <math>1/2 < p < 1</math>. Desweiteren wird von einem ''konsistenten'' Algorithmus gesprochen, wenn er nie zwei verschiedene richtige Lösungen für dasselbe Problem liefert.
Es gibt auch Monte-Carlo-Algorithmen, welche nicht nur den zu lösenden Fall als Argument akzeptieren, sondern auch eine obere Schranke für die zulässige Wahrscheinlichkeit eines Fehlers. Die benötigte Rechenzeit lässt sich dann als Funktion der Größe des zu bearbeitenden Falls und des Kehrwerts der zulässigen Fehlerwahrscheinlichkeit ausdrücken.
Um die Erfolgswahrscheinlichkeit eines Monte-Carlo-Algorithmuses heraufzusetzen muss er nur mehrmals ausgeführt werden und anschließend das häufigste Ergebnis ausgewählt werden.
===Äquivalenz zweier Multimengen===
Ein Beispiel für einen Monte-Carlo-Algorithmus ist der Test zweier Multimengen auf Äquivalenz. In Multimengen können mehrere gleiche Elemente enthalten sein. Im Beispiel werden Multimengen betrachtet, deren Elemente natürliche Zahlen aus <math>[1, k]</math> (mit <math>k \in N</math>) sind.
zum Beispiel:
* <math>M_1 = \lbrace 2,3,4,2,2,3 \rbrace </math>
* <math>M_2 = \lbrace 3,4,2,3,2,2 \rbrace </math>
* <math>M_3 = \lbrace 3,4,2,3,3,2 \rbrace </math>
Der klassische Weg eine Entscheidung über die Äquivalenz der Multimengen zu treffen, wäre sie zu sortieren und anschließend elementweise zu vergleichen. Dies kostet jedoch im Mittel <math>O~(n~log~n)</math>. Mit einem probabilistischen Algorithmus ist man in der Lage das Problem in <math>\theta~(n)</math> zu lösen.
Dazu wird der Multimenge
<math>M_1~=~(x_1,x_2,~...~,x_n)</math> ein Polynom <math>p_m_1</math> mit <math>p_m_1(x)~=~(x~-~x_1)(x~-~x_2)~...~(x~-~x_n)</math> und
der Multimenge <math>M_2~=~(y_1,y_2,~...~,y_n)</math> ein Polynom <math>p_m_2</math> mit <math>p_m_2(x)~=~(x~-~y_1)(x~-~y_2)~...~(x~-~y_n)</math>
zugeordnet.
Die (evtl. mehrfachen) Nullstellen von <math>p_m_1~(x)</math> heißen <math>x_1,x_2,~...~,x_n</math> und die von <math>p_m_2~(x)</math> sind <math>y_1,y_2,~...~,y_n</math>.
Diese Darstellung ist für jede ganzrationale Funktion eindeutig. Demzufolge gilt <math>M_1~\equiv~M_2 </math> genau dann wenn <math>p_m_1~(x)~=~p_m_2(x)</math>.
Mit folgendem Code kann der Polynomwert einer Multimenge bestimmt werden.
<code id="4dd52c5139926">
int[] m1 = {2,3,4,2,2,3};
int[] m2 = {3,4,2,3,2,2};
int[] m3 = {3,4,2,3,3,2};
static int polynomWert(int[] menge, int x){
int i = menge.length;
int wert = 1;
if(i == 0)
return 1;
else
for(i = menge.length; i > 0; i--){
wert = wert * (x - menge[i-1]);
}
return wert;
}
</code>
<run id="4dd52c513999d">System.out.println("Das Polynom hat den Wert " + polynomWert(m1,9));</run>
Berechnet und vergleicht man nun die Polynomwerte zweier Multimengen mit einer beliebiegen Testzahl <math>x'</math> und erhält verschiedene Werte für <math>p_m_1~(x')</math> und <math>p_m_1~(x')</math> so weiß man definitiv das <math>M_1~\not\equiv~M_2 </math>.
[[Datei:Multimengenvergleich.JPG|300px|thumb|right|Graphen der Polynome <math>pm_1(x)</math> und <math>pm_3(x)</math>]]
Wie die Abbildung rechts zeigt haben die unterschiedlichen Polynome <math>pm_1(x)</math> und <math>pm_2(x)</math> an mehreren Stellen die gleichen Funktionswerte. Trifft man mit einem zufällig gewählten x eine dieser Stellen erhält man möglicherweise ein falsches Ergebnis.
Um das zu vermeiden wiederholt man den Test bei Erfolg mehrere Male. Somit ist es möglich, dass richtige Ergebnis mit hoher Wahrscheinlichkeit zu erhalten.
<code id="4dd7c4f022df0">
java.util.Random random = new java.util.Random();
boolean aequiv (int r, int[] a, int[] b, int wdh){
int x = random.nextInt(r);
if(polynomWert(a,x) == polynomWert(b,x)){
if(wdh >= 0){
this.aequiv (r, a, b, wdh - 1);
}
return true;
}
else {return false;}
}
</code>
<run id="4dd7c4f022ec1">System.out.println(aequiv (100, m1, m2, 10))</run>
===Primzahltest nach FERMAT===
[[Bild:S3makuba_Primzahlen.jpg]]
====Algemein:====
Unter einer Primzahl versteht man eine Zahl die nur durch 1 und sich selbst teilbar ist. Mit Probeteilern ist es natürlich möglich herauszufinden ob eine Zahl als Primzahl gedeutet werden kann oder nicht . Diese Form der Primzahlfindung bringt jedoch bei Zahlen mit hoher stelligkeit sehr wenig und würde sehr zeitaufwändig werden.
Eine viel effizientere Lösung bringt der "Primzahltest nach Fermat".Diesen Test kann man durch einfügen von Zufallszahlen(randomisieren) zu einen Monte-Carlo-Algorithmus umwandeln . Um die Basis dafür zu schaffen benötigt man zu aller erst den "Satz von EULER"
=====Satz von Euler=====
Für alle natürlichen Zahlen <math>n</math> und <math>a</math> mit <math>n \geq 2</math> und <math>1 \leq a < n</math>, wobei <math>ggt(a,n)=1</math>, gilt <math>a^{\varphi(n)}\equiv 1\ mod\ n</math>
Auf diesen Satz kann man nun den "kleinen Satz von Fermat " anwenden.
=====kleiner Satz von Fermat=====
Wenn <math>n</math> eine Primzahl ist, dann gilt für alle natürlichen Zahlen <math>a</math> (mit<math> 1\geq a \geq n - 1)</math>
<math>a^{primzahl}\equiv a (mod\ prim)</math>
Hat man diese beiden Sätze nun kann man auf folgenden Satz daraus Bilden:
<math>a^{primzahl-1}\equiv 1 (mod\ prim)</math>
Bei diesen "Primzahltest von Fermat" gibt es jedoch auch Zahlen die die Eigenschaften des Satzes haben ,aber trotdem keine Primzahlen sind.
Diese Arten von Zahlen teilen sich auf in '''Pseudoprimzahlen''' und '''Carmickel Zahlen'''.
=====Pseudoprimzahlen=====
Eine Fermatsche Pseudoprimzahl ist eine zusammengesetzte, natürliche Zahl n, zu der mindestens eine natürliche Zahl a mit ggT(a, n) = 1 und a > 1 existiert, so das:
(1) a^{n-1} /equiv 1 mod n , gilt.
Man sagt zu diesen Zahlen auch: "n ist pseudoprim zur Basis a".
'''Beispiel:'''
Die Zahl 341 ist eine zusammengesetzte Zahl aus 11*31 und dennoch bestimmt der "Primzahltest von Fermat" sie als Primzahl.
<math>2^{340} \equiv 1\mod\ 341
</math>
Pseudoprimzahlen für Basen 2,3,und 5:
'''Basis 2'''
341, 561, 645, 1105, 1387, 1729, 1905, …
'''Basis 3'''
91, 121, 286, 671, 703, 949, 1105, 1541, 1729, …
'''Basis 5'''
====Carmichael Zahlen====
Diese Zahlen wurden nach dem Mathematiker Robert Daniel Carmichael benannt.
Eine natürliche Zahl heißt Carmichael-Zahl, wenn sie eine fermatsche Pseudoprimzahl bezüglich aller zu ihr teilerfremden Basen ist.
'''Definition:'''
Eine zusammengesetzte natürliche Zahl n heißt Carmichael-Zahl, falls für alle zu n teilerfremden Zahlen a die folgende Kongruenz erfüllt ist:
<math>a^{n-1}\equiv 1 (mod\ n)</math>
Beispiel:
Die kleinste Carmichael Zahl ist 561 . Diese kann man leicht aus Primzahlen zusammensetzen 561= 3·11·17 . Für alle Basen a, die keinen Primfaktor mit 561 gemeinsam haben, gilt nämlich a^560 ≡ 1 mod 561.
561 ist durch 3, 11, 17, 33, 51 und 187 teilbar.
Für diese Teiler gilt die Kongruenz jedoch nicht:
<math>3^{560} \equiv 375\ (mod\ 561),</math>
<math>11^{560} \equiv 154\ (mod\ 561),</math>
<math>17^{560} \equiv 34\ (mod\ 561),</math>
usw.
====Probabilistischer Primzahltest:====
Bei dem Probabilistischen Primzahltest wird davon ausgegangen das die Basis zufällig gewählt wird .Dadurch wird die Zeitkomplexität sehr stark verbessert ,jedoch kann es vorkommen das Falsche Ergebnisse herauskommen.Diese Möglichkeit kann man veringern indem man den Primzahltest mehrere male laufen lässt .
===Primzahltest von Solovay und Strassen===
Dieser Test wurde 1977 entwickelt und findet heute vor allem in der Kryptographie Anwendung, da er Geschwindigkeitsvorteile gegenüber derterministischen Tests mit sich bringt. Bis 2002 existierte kein deterministischer Algorithmus der in der Lage war in polynominellem Zeitaufwand eine Zahl auf ihre Primzahleigenschaften zu testen.
Es wird zuerst zufällig ein <math>a < n </math> mit <math>ggt(a,n) = 1</math> gewählt. Anschließend berechnt man die ''Jacobi-Funktion'', die wie folgt definiert ist.
<math> J(a,n)=\begin{cases}1,& ,falls~a = 1 \\ J(\frac{a}{2},n)*(-1)\frac{n^2-1}{8} & ,falls~a= gerade \\ J(rest(n,a)*(-1)^(a-1)^\frac{n-1}{4} & ,sonst\end{cases} </math>
Wie das Beispiel zeigt kann die ''Jacobi-Funktion'' nur die Werte +1 oder -1 annehmen.
<code id="4de113d588b04" hidden>double ggt(double x, double y){
double g;
if(x<0)
x = -x;
if(y<0)
y = -y;
g = y;
while (x>0)
{
g = x;
x = y % x;
y = g;
}
return g;
}</code>
<code id="4de113d588bd3" hidden> boolean TestKongruenz(double a, double n){
double myNumber = a;
double myExponent = ((n-1));
double myTotal;
myTotal = Math.pow(myNumber, myExponent/2);
if(myTotal % n == (((JacobiSymbol(a, n)) % n) + n) %n){
return true;
}
else return false;
}</code>
<popup name = "vollständigen Java Code">
<code id="4de113d588c7e">double JacobiSymbol(double a, double n){
{
double j = 1;
a = a % n;
if (a < 0)
a = a + n;
while (a != 0)
{
while (a % 2 == 0)
{
a = a / 2;
double res = n % 8;
if (res == 3 || res == 5)
j = -j;
}
double temp = a;
a = n;
n = temp;
if (((a % 4) ==3) && ((n % 4) ==3))
j = -j;
a = a % n;
}
if (n==1)
return j;
else
return 0;
}}</code>
</popup>
<run id="4de113d588f0e">System.out.println(JacobiSymbol(3, 7))</run>
Nun gilt folgender Satz:
Wenn <math>n</math> eine Primzahl ist, dann gilt für alle <math>a \in N</math> (mit <math>1 < a \le n - 1 </math> und <math> ggT(a,n) = 1</math>):
<math>J(a,n) \equiv a \frac{n-1}{2} mod~n</math>.
<code id="4de113d588d22" hidden>
java.util.Random random = new java.util.Random();
int definea(int n){
int a;
do{
a = random.nextInt(n) + 2;
}
while(ggt(a, n) != 1 && a % 2== 0);
return a;
}
</code>
<code id="4de113d588dd2">void TestPrim(int n){
if(TestKongruenz(definea(n), n) == true)
System.out.println(n + " ist eine Primzahl");
else System.out.println(n + " ist keine Primzahl");
}</code>
<run id="4de113d588fb1">TestPrim(7);</run>
Falls <math>n</math> eine Primzahl ist liefert der Test definitiv das korrekte Ergebnis. Andernfalls mit einer Wahrscheinlichkeit von <math><~\frac{1}{2}</math> ein falsches Ergebnis. Durch mehrfaches Ausführen lässt sich die Fehlerwahrscheinlichkeit bei <math>k</math> Versuchen auf <math>\frac{1}{2^k}</math> reduzieren.
==Übungen:==
*[[AuK/Probabilistische Algorithmen SS11/|Übungsaufgaben]]
==Quellen==
* Christian Wagenknecht: ''Algorithmen und Komplexität'', Fachbuchverlag Leipzig, 2003,
* Brassard, Gilles; Bratley, Paul: ''Algorithmik: Theorie und Praxis'', Attenkirchen: Wolfram, 1993
* Sebastian, Rick;Jörg, Wiesner: ''Studienarbeit: Probabilistische Algorithmen'',:Görlitz, 2008