import Prog1Tools.IOTools;
import java.lang.Math;
import java.util.Random;
import java.math.BigInteger;
class Primzahl {
Random ran = new Random();
BigInteger zero = BigInteger.ZERO;
BigInteger one = BigInteger.ONE;
public static void main(String[] args) {
Primzahl prim = new Primzahl();
boolean a = true;
System.out.println("Bruto Force (1)");
System.out.println("Fermat (2)");
System.out.println("Miller (3)");
System.out.println("Euler (4)");
System.out.println("Giuga (5)");
System.out.println("Wilson (6)");
System.out.println("Primfaktorzerlegung (7)");
System.out.println("Abbrechen (8)");
while(a) {
System.out.print("\nWaehle Algorithmus : ");
int zahl = IOTools.readInteger();
switch (zahl) {
case 1: prim.bruto() ; break;
case 2: prim.fermat() ; break;
case 3: prim.miller() ; break;
case 4: prim.euler() ; break;
case 5: prim.giuga() ; break;
case 6: prim.wilson() ; break;
case 7: prim.zerlegung(); break;
case 8: a=false ; break;
default: System.out.println("Falsche Eingabe!");
}
}
}
/*
** Brute Force
**
** es wird für 2 < i < eingabe
** versucht einen teiler für eingabe zu finden
** wenn dem so ist, ist eingabe keine Primzahl
*/
public void bruto() {
System.out.print("Eingabe: ");
BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
boolean test = true;
for(int i = 2; i < eingabe.intValue(); i++)
if(eingabe.mod(BigInteger.valueOf(i)).compareTo(zero)==0)
test = false;
if(test)
System.out.println(eingabe +" ist Primzahl");
else {
System.out.println(eingabe +" ist keine Primzahl");
zerlegung(eingabe.intValue());
}
}
/*
** Der kleine Satz von Fermat
**
** Für jede ganze Zahl a, die nicht durch p teilbar ist gilt:
** a^(p-1) mod p = 1 mod p <=> a^p mod p = a mod p
** a: zufällig gewählt mit 0 < a < eingabe
**
** Durch umformen : a^p mod p = a
*/
public void fermat() {
System.out.print("Eingabe: ");
BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
boolean teiler = true;
BigInteger a = BigInteger.valueOf(0);
while(teiler) {
a = new BigInteger(eingabe.bitLength(),ran); //Zufallszahl
a.add(one);
if(ggT(a,eingabe).compareTo(one) == 0)
teiler=false;
}
if(a.modPow(eingabe,eingabe).compareTo(a) == 0)
System.out.println(eingabe +" ist Primzahl");
else {
System.out.println(eingabe +" ist keine Primzahl");
zerlegung(eingabe.intValue());
}
}
/*
** Miller-Rabin-Test
**
** Es gilt: a^d mod n = 1 mod n oder a^(d*2^r) mod n = -1 mod n
** mit (n-1) = d*2^s
** a: zufällig gewählt mit 1 < a < n
** s: größte Zahl die (n-1) mit 2^r teilt (n-1)/(2^r)
** d: ist dann das ergebnis von (n-1)/(2^r) muss ebenfalls ? N sein
**
** Durch umformen : (a^d -1) mod n = 0 oder (a^(d*2^r)+1) mod n = 0
**
** r wird hier getestet mit: 0 < r < (s-1)
*/
public void miller() {
System.out.print("Eingabe: ");
BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
System.out.print("Zeugen: ");
BigInteger zeugen = BigInteger.valueOf(IOTools.readInteger());
boolean test = false;
BigInteger two = BigInteger.valueOf(2);
for(int z=0; z < zeugen.intValue(); z++) {
BigInteger s = zero;
BigInteger basis = new BigInteger(eingabe.bitLength()-1,ran); //Zufallszahl
for(int i=1; eingabe.subtract(one).intValue() < Math.pow(2,i);i++) {
if(eingabe.subtract(one).mod(BigInteger.valueOf((long)Math.pow(2,i))).compareTo(zero)==0)
s=BigInteger.valueOf(i);
}
BigInteger d = eingabe.subtract(one).divide(BigInteger.valueOf((long)Math.pow(2,s.intValue())));
if(basis.modPow(d,eingabe).subtract(one).compareTo(zero) == 0)
test = true;
for(int r = 0;r <= s.subtract(one).intValue();r++)
if( basis.pow(d.multiply(two.pow(r)).intValue()).add(one).mod(eingabe).compareTo(zero)== 0)
test = true;
}
if(test)
System.out.println(eingabe +" ist Primzahl");
else {
System.out.println(eingabe+" ist keine Primzahl");
zerlegung(eingabe.intValue());
}
}
/*
** Euler und das Legendre-Symbol
**
** Für jede ungerade Primzahl p und jede ganze Zahl a,
** die nicht durch p teilbar ist, gilt:
** a^((p-1)/2) mod p = 1 mod p oder a^((p-1)/2) mod p = -1 mod p
**
** Durch umformen : (a^((p-1)/2)-1) mod p = 0 oder (a^((p-1)/2)+1) mod p = 0
*/
public void euler() {
System.out.print("Eingabe: ");
BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
BigInteger two = BigInteger.valueOf(2);
BigInteger a = new BigInteger(eingabe.bitLength()-1,ran); //Zufallszahl
a = a.modPow((eingabe.subtract(one)).divide(two),eingabe);
if(a.compareTo(one) == 0)
System.out.println(eingabe + " ist Primzahl");
else if(a.compareTo(eingabe.subtract(one)) == 0)
System.out.println(eingabe + " ist Primzahl");
else {
System.out.println(eingabe + " ist keine Primzahl");
zerlegung(eingabe.intValue());
}
}
/*
** Giuga
**
** Aus dem kleinen Satz von Fermat folgt, dass für eine Primzahl p gilt:
** 1^(p-1)+2^(p-1)+ ... +(p-1)^(p-1) mod p = -1 mod p
**
** Durch umformen : (1^(p-1)+2^(p-1)+ ... +(p-1)^(p-1) + 1) mod p = 0
*/
public void giuga() {
System.out.print("Eingabe: ");
BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
BigInteger erg = BigInteger.valueOf(0);
for(int i = 1;i < eingabe.intValue();i++){
erg = erg.add(BigInteger.valueOf(i).pow(eingabe.subtract(one).intValue()));
}
if(erg.add(one).mod(eingabe).compareTo(zero)==0)
System.out.println(eingabe +" ist Primzahl");
else {
System.out.println(eingabe +" ist keine Primzahl");
zerlegung(eingabe.intValue());
}
}
/*
** Wilson
** Er besagt: Genau dann ist p > 1 eine Primzahl, wenn
** (p-1)! mod p = -1 mod p
**
** Durch umformen : ((p-1)! + 1) mod p = 0
*/
public void wilson() {
System.out.print("Eingabe: ");
BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
BigInteger f = fak(eingabe.subtract(one));
if(f.add(one).mod(eingabe).compareTo(zero)==0)
System.out.println(eingabe +" ist Primzahl");
else {
System.out.println(eingabe +" ist keine Primzahl");
zerlegung(eingabe.intValue());
}
}
// Fakultät
public BigInteger fak(BigInteger i) {
if(i.compareTo(zero)==0 || i.compareTo(one)==0)
return one;
else return i.multiply(fak(i.subtract(one)));
}
// ggT
public BigInteger ggT(BigInteger n, BigInteger m) {
if( n.compareTo(zero) == 0 || m.compareTo(zero) == 0)
return zero;
else {
while(n.compareTo(m) != 0) {
if(n.compareTo(m) == 1)
n = n.subtract(m);
else
m = m.subtract(n);
}
return n;
}
}
/*
** Primfaktorzerlegung
**
** via Sieb des Eratosthenes alle Primzahlen bis n herrausfinden
** und dannach mit der größten beginnend durch n teilen
** und somit die Primfaktoren ausfindig machen falls vorhanden
*/
public void zerlegung() {
System.out.print("Zahl: ");
int n = IOTools.readInteger();
String exp = "";
boolean gestrichen [] = new boolean[n];
boolean einmal = false;
int prim = 2;
for(int i =2 ; i<n; i++)
gestrichen[i] = false;
while((prim*prim) <= n) {
if(gestrichen[prim] == false)
for (int j = 2; prim*j<n;j++)
gestrichen[prim*j] = true;
prim = prim +1;
}
for(int i = (n-1); i>1 ; i--) {
if(gestrichen[i] == false) {
boolean j = true;
int zahl=0;
while(j) {
if(n%i == 0){
zahl++;
n = n/i;
einmal = true;
}
else
j = false;
}
if(zahl != 0)
exp = exp + i + "^" + zahl + " * ";
}
}
if(einmal) {
exp = exp.substring(0, exp.length() - 2);
System.out.println(exp);
}
else
System.out.println("Es gibt keine Primfaktorzerlegung ");
}
// Nochmal für die nicht Primzahlen wird automatisch aufgerufen
public void zerlegung(int n) {
String exp = "";
boolean gestrichen [] = new boolean[n];
boolean einmal = false;
int prim = 2;
for(int i =2 ; i<n; i++)
gestrichen[i] = false;
while((prim*prim) <= n) {
if(gestrichen[prim] == false)
for (int j = 2; prim*j<n;j++)
gestrichen[prim*j] = true;
prim = prim +1;
}
for(int i = (n-1); i>1 ; i--) {
if(gestrichen[i] == false) {
boolean j = true;
int zahl=0;
while(j) {
if(n%i == 0){
zahl++;
n = n/i;
einmal = true;
}
else
j = false;
}
if(zahl != 0)
exp = exp + i + "^" + zahl + " * ";
}
}
if(einmal) {
exp = exp.substring(0, exp.length() - 2);
System.out.println(exp);
}
else
System.out.println("Es gibt keine Primfaktorzerlegung ");
}
}
![[HaBo]](/styles/default/logoklein.png){kind=small}
