[bearbeitet durch Martin Kell]
Die hier erstellte Klasse soll anfangs eine einfache PrimzahlenKlasse sein, die später dann zu einer allgemeinen Numerik-Klasse ausgebaut werden soll (download).
Theoretische Voraussetzungen
Software
|
Zunächst noch einmal zur Wiederholung die Definition einer Primzahl.
| Eine Primzahlen ist eine positive ganze Zahl die genau zwei Teiler hat. Nämlich 1 und sich selbst. Deshalb ist 1 keine Primzahl. |
Da eine Primzahl p nur durch Eins und sich selbst teilbar sein darf, kann ein einfacher Test sein, zu prüfen, ob alle Zahlen von 2 bis p-1 nicht Teiler von p sind. Hier der Auschnitt der Methode:
...
public boolean isPrimeSimple(int p) {
if(p < 2) { // jede Zahl kleiner als 2 ist KEINE Primzahl
return false;
}
for(int i = 2; i < p; i++) { // alle Zahlen von 2 bis p-1
if(p % i == 0)
return false;
}
return true;
}
...
|
Da dieser Test sehr ineffizient ist, müsste man ihn verbessern. Zunächst braucht
man nicht alle Zahlen von 1 bis p-1 zu prüfen. Die größte Zahl die man zu prüfen muss, wäre
p/2. Wenn jedoch p/2 ein Teiler von p ist so muss auch 2 ein Teiler von p sein. (Genauso für alle
anderen Zahlen.) D.h. man prüft einfach die für p "kleinsten" Teiler, diese sind alle Zahlen kleiner
gleich oder gleich der Wurzel(p).
Um nun nur möglichst "vermutliche" Primzahlen zu testen, benutzt man die Eigenschaft, dass jede Primzahl
größer als 3 mit der Formel 6·x ± 1 dargestellt werden kann.
...
public boolean isPrimeExt(int p) {
if(p < 2)
return false;
if(p == 3 || p == 2)
return true;
// Zahl darf nicht durch 2 oder 3 teilbar sein.
if(p < 5 && (p % 2 == 0 || p % 3 == 0))
return false;
// (ganzzahlig) wurzel + 1 bilden
int wurzel = (int) java.lang.Math.sqrt((double)p) + 1;
// von 5 (= 6*1 - 1) bis max. ein Schritt über die Wurzel.
for(int i = 1; 6*i - 1 < wurzel; i++) {
if(p % (6*i - 1) == 0)
return false;
if(p % (6*i + 1) == 0)
return false;
}
return true;
}
...
|
Die Exponentiation einer Zahl a hoch b modulo n kann sehr einfach rekursive implementiert. Hier die Fälle für den rekursiven Ablauf:
|
Algorithmus als Rekursion:
1. 3 ^ 19 mod 23 = 3 ^ (18 + 1) mod 23 = 3*(3 ^ 18) mod 23 2. 3 ^ 18 = 3 ^ (2*9) mod 23 = (3^9)^2 mod 23 3. 3^9 mod 23 = 3 ^ (8 + 1) mod 23 = 3 * (3 ^ 8) mod 23 4. 3 ^ 8 mod 23 = 3 ^ (2*4) mod 23 = (3 ^ 4) ^ 2 mod 23 5. 3 ^ 4 mod 23 = 3 ^ 2*2 mod 23 = (3 ^ 2) ^ 2 mod 23 6. 3 ^ 2 mod 23 = = 3 ^ 2*1 mod 23 = (3 ^ 1) ^ 2 mod 23 7. 3 ^ 1 mod 23 = 3 6. (3 ^ 1) ^ 2 mod 23 = 3 ^ 2 mod 23 = 9 5. (3 ^ 2) ^ 2 mod 23 = 9 ^ 2 mod 23 = 12 4. (3 ^ 4) ^ 2 mod 23 = 12 ^ 2 mod 23 = 6 3. 3 * (3 ^ 8) mod 23 ) = 3 * 6 mod 23 = 18 2. (3 ^ 9) ^ 2 = 18 ^ 2 mod 23 = 2 1. 3 * (3 ^ 18) = 3 * 2 mod 23 = 6 --> 3 ^ 19 mod 23 = 6
...
public int modExp(int a, int b, int n) {
// bringt a und b in Bereich von n
a = a % n;
b = b % n;
if(n*n < 0) // Bereichsprüfung (kein int-Überlauf)
return -1;
// Rekursionsabbruch und Absicherung
if(a == 0) // 0^b = 0
return 0;
if(a == 1 || b == 0) // 1^a == 1, x^0 = 1
return 1;
if(b == 1) // a^1 == a
return a;
// Halbierungsexponentiation
if(b % 2 == 0) {
a = modExp(a, b/2, n); // a ^ 2c mod n = (a^c)^2 mod n
return (a*a) % n;
} else
return (a*modExp(a, b-1, n)) % n; // a ^ (2c+1) = a * a^2c mod n
}
...
|
Der kleine Satz von Fermat besagt, dass für jede Primzahl p gilt (a sei eine Zahl von 1 bis p-1):
a ^ (p-1) mod p = 1Dieser ALgorithmus ist mit Hilfe der schnellen modularen Expontiation leicht zu implementieren. Da es leider Zahlen - sogenannte Carmichael-Zahlen - gibt die den Test mit allen Zahlen a bestehen, bezeichnet man diesen Test als Pseudoprimzahlen-Test. Die kleinste Carmichael-Zahl ist 561 (durch 3 teilbar). Desweiteren bezeichnet man diesen Test nur als PseudoTest, weil man nicht alle Zahlen testen kann/soll.
...
boolean isPrimeFermat(int p, int t) {
// t gibt Anzahl der Test an.
for(int i = 0; i < t; i++) {
int a = (int)(java.lang.Math.random() * (double)p);
if(modExp(a, p-1, p) != 1)
return false;
}
return true;
}
...
|
Da wir jetzt ausreichend Tests zur Primzahlenfindung haben, können wir eine Primzahlen-Suche implementieren. Da diese "exakter" sein soll, benutzen wir erst den schnellen Fermat-Test und zur Absicherung falls dieser erfolgreich ist, den erweiterten Test.
...
int getNextPrime(int n) {
if(n == 1)
return 1;
if(n % 2 == 1) // nur ungerade Zahlen !!
n++;
n++; // Zahl nach n wird zuerst geprüft (sollte jetzt immer ungerade sein)
int p = -1; // noch keine primzahl gefunden
while(true) {
if(n*n < 0) { // bereichsprüfung (für schnelle Exponentiation nur 31/63bit möglich)
p = -1;
break;
}
p = n;
// auswertung durch isPrimeExt erst wenn isPrimeFermat wahr ist.
if(isPrimeFermat(n, 4) && isPrimeExt(n))
break;
n += 2; // immer ungerade Zahlen
}
return p;
}
...
|