Downloads
| Fermats Faktorisierungsverfahren in Java |
| Monday, 10 March 2008 00:52 |
|
Hier meine Implementierung in Java, die sich aber wegen des eingeschränkten Wertebereichs von int nur für kleinere Zahlen eignet: public void calcfermat(int n){ int y,a,b = 0; int x = (int)Math.sqrt(n)+1; int r = (int)Math.pow(x,2)-n; double temp = Math.sqrt(r); while(temp - (int)temp!=0){ //check if squarenumber r = 2*x + r + 1; x++; temp = Math.sqrt(r); } y = (int)temp; a = x + y; b = x - y; System.out.println("Factorization of "+n+": "+a+","+b); }
Um die Einschränkungen durch den begrenzten Wertebereich von int zu umgehen, hier meine Implementierung mit Hilfe von BigInteger. Leider gibt es für BigInteger noch keine Methode zur Berechnung der Wurzel so dass man diese selbst implementieren muss. Ungünstig ist außerdem im Moment noch die Überprüfung des Abbruchkriteriums gelöst (Prüfe ob Wert == (v(Wert))²): public void calcfermatbigint(BigInteger n){ BigInteger y,a,b = BigInteger.valueOf(0); BigInteger x = sqrt(n).add(BigInteger.ONE); BigInteger r = x.pow(2).subtract(n); BigInteger temp = sqrt(r); while(r.compareTo(temp.pow(2)) != 0){ //bad compare method r = r.add(x.multiply(BigInteger.valueOf(2))); r = r.add(BigInteger.ONE); x = x.add(BigInteger.ONE); temp = sqrt(r); } y = temp; a = x.add(y); b = x.subtract(y); System.out.println("Factorization of "+n+": "+a+","+b); } public static BigInteger sqrt(BigInteger val){ BigInteger two = BigInteger.valueOf(2); BigInteger a = BigInteger.ONE.shiftLeft(val.bitLength()/2); BigInteger b; do{ b = val.divide(a); a = (a.add(b)).divide(two); } while (a.subtract(b).abs().compareTo(two) >= 0); return a; }
In der ersten Implementierung wurde relativ ineffizient überprüft, ob die r eine Quadratzahl ist. Dies lässt sich effizienter, wenn auch mit ein paar Zeilen mehr Code lösen. Ob eine Zahl überhaupt eine Quadratzahl sein kann, lässt sich an ihren letzten beiden Ziffern sehen. Eine Quadratzahl endet immer mit 00, x1, x4, 25, y6 und x9, wobei x für eine gerade und y für eine ungerade Ziffer steht. [Quelle: Wikipedia] Dadurch ergibt sich ein javaspezifisches Problem, da Java für BigInteger keine Methode anbietet, mit der sich direkt bestimmte Ziffern auslesen lassen. Durch eine Konvertierung in String und Parsen in int geht allerdings die meiste gewonnene Geschwindigkeit wieder verloren. Um das zu vermeiden habe ich zum Ermitteln der letzten Ziffern den Modulo verwendet. public BigInteger[] calcfermatbigint(BigInteger n){ BigInteger y = BigInteger.valueOf(0); BigInteger x = sqrt(n).add(BigInteger.ONE); BigInteger r = x.pow(2).subtract(n); while(!checkifsquarenumber(r)){ r = r.add(x.multiply(BigInteger.valueOf(2))); r = r.add(BigInteger.ONE); x = x.add(BigInteger.ONE); } y = sqrt(r); BigInteger array[] = new BigInteger[2]; array[0] = x.add(y); array[1] = x.subtract(y); return array; } private static final BigInteger b100 = new BigInteger("100"); public static boolean checkifsquarenumber(BigInteger r){ boolean check = false; int y = (int)r.mod(b100).longValue(); int lc1 = y / 10; int lc2 = y % 10; if(lc1%2==0){ //second last number is even if(lc2 == 1 || lc2 == 4 || lc2 == 9){ BigInteger temp = sqrt(r); if(r.compareTo(temp.pow(2)) == 0){ check = true; } } } else{ if(lc2 == 6 || lc2 == 9){ BigInteger temp = sqrt(r); if(r.compareTo(temp.pow(2)) == 0){ check = true; } } } if(lc1 == 0){ if(lc2 == 0){ BigInteger temp = sqrt(r); if(r.compareTo(temp.pow(2)) == 0){ check = true; } } } if(lc1 == 2){ if(lc2 == 5){ BigInteger temp = sqrt(r); if(r.compareTo(temp.pow(2)) == 0){ check = true; } } } return check; } public static BigInteger sqrt(BigInteger val){ BigInteger two = BigInteger.valueOf(2); BigInteger a = BigInteger.ONE.shiftLeft(val.bitLength()/2); BigInteger b; do{ b = val.divide(a); a = (a.add(b)).divide(two); } while (a.subtract(b).abs().compareTo(two) >= 0); return a; }
Im Vergleich mit der ersten Implementierung hat sich die Laufzeit ungefähr halbiert. |