schnelle Primfaktorzerlegung und isProbablePrime
Carsten Hammer
gibt es fertige Klassen für schnelle Primfaktorzerlegungen in Java?
Wenn ich bei der folgenden Klasse in der Methode boolean isPrim(int n)
den certainty Wert beim Aufruf von isProbablePrime(10) von 10 auf 1
verringere dann tanzen die Primfaktoren ein bischen herum beim resizen
von der JTable. Offensichtlich sind Aufrufe der Methode isProbablePrime
nicht unbedingt mehr exakt reproduzierbar mit so kleinen Werten bzw. von
Aufruf zu Aufruf kann sich das Ergebnis ändern.
Die Klasse unten ist natürlich mit heisser Nadel gestrickt. Kann ich
isProbablePrime irgendwie aufrufen, dass ich den Ergebnissen trauen kann?
Tschö,
Carsten
package primtest;
import javax.swing.table.*;
import java.math.BigInteger;
/**
* <p>Title: </p>
* <p>Description: Table Model um die Primfaktorzerlegungen von ganzen
Zahlen anzuschauen</p>
* <p>Copyright: Copyright (c) 2004</p>
* <p>Company: </p>
* @author Carsten Hammer
* @version 1.0
*/
public class primfaktorzerlegungTableModel
extends AbstractTableModel {
public primfaktorzerlegungTableModel() {
}
/**
* Tested ob n eine Primzahl ist
* @param n int
* @return boolean
*/
public boolean isPrim(int n) {
BigInteger bla = new BigInteger(new Integer(n).toString());
return bla.isProbablePrime(10);
}
/**
* Gebe die n te Primzahl zurück
* @param n int
* @return int
*/
public int getNprim(int n) {
int i = 0; // Nummer der Primzahl
int a = 0; // Zahl, die auf Primzahl getestet wird
while (i < n) {
a++;
if (isPrim(a)) {
i++;
}
}
return a;
}
/**
* Wie oft steckt prim in i?
* @param prim int
* @param i int
* @return int
*/
public int getPriminI(int prim,int i){
int a=i;
int count=0;
while(a%prim==0){
a= a / prim;
count++;
if(a==0)break;
}
return count;
}
public int getRowCount() {
return 10000;
}
public int getColumnCount() {
return 100;
}
public Object getValueAt(int rowIndex, int columnIndex) {
if(columnIndex==0)return new Integer(rowIndex);
int columnprim=this.getNprim(columnIndex);
int bla=this.getPriminI(columnprim,rowIndex);
if(bla>0){
return new Integer(bla);
}else{
return "";
}
}
/**
* Returns the name of the column at <code>columnIndex</code>.
*
* @param columnIndex the index of the column
* @return the name of the column
* @todo Implement this javax.swing.table.TableModel method
*/
public String getColumnName(int columnIndex) {
return "" + this.getNprim(columnIndex);
}
}
Marco Lange
> gibt es fertige Klassen für schnelle Primfaktorzerlegungen in Java?
> Wenn ich bei der folgenden Klasse in der Methode boolean isPrim(int n)
> den certainty Wert beim Aufruf von isProbablePrime(10) von 10 auf 1
> verringere dann tanzen die Primfaktoren ein bischen herum beim resizen
> von der JTable. Offensichtlich sind Aufrufe der Methode isProbablePrime
> nicht unbedingt mehr exakt reproduzierbar mit so kleinen Werten bzw. von
> Aufruf zu Aufruf kann sich das Ergebnis ändern.
Ja, isProbablePrime ist ein randomisierter Algorithmus, der somit nicht
deterministisch arbeitet. Genauer gesagt basiert die Methode auf dem
Rabin-Miller-Algorithmus (zumindest teilweise), der wiederum auf
Erkenntnissen aus der Algebra / Zahlentheorie (genauer: auf dem kleinen
Satz von Fermat und den Erkenntnissen über die Carmichael-Zahlen)
beruht. Näheres zur Funktionsweise des Rabin-Miller-Algorithmus solltest
Du u.a. mit Google finden können.
Es gibt deterministische Primzahltests, die glaube ich in O(n^12) oder
O(n^6) laufen, aber die sind damit häufig noch um ein vielfaches
langsamer als der Rabin-Miller-Algorithmus, der wirklich relativ gut
ist. Ob es dort eine Java-Implementierung gibt, weiß ich nicht, ich
kenne nicht einmal den Algorithmus genau.
Eine effiziente Primfaktorzerlegung wirst Du kaum finden, denn das ist
nach wie vor ein offenes Problem. (Oder hat irgendjemand schon die
NP-vollständigkeit der Primfaktorzerlegung bewiesen. Na ja, selbst wenn,
dann wäre es immer noch offen...)
Viele Grüße,
Marco
Carsten Hammer
sonst arg langsam auf aelteren rechnern..
package primtest;
import javax.swing.table.*;
import java.math.BigInteger;
import java.util.HashMap;
/**
* <p>Title: </p>
* <p>Description: Table Model um die Primfaktorzerlegungen von ganzen
Zahlen anzuschauen</p>
* <p>Copyright: Copyright (c) 2004</p>
* <p>Company: </p>
* @author Carste Hammer
* @version 1.0
*/
public class primfaktorzerlegungTableModel
extends AbstractTableModel {
public primfaktorzerlegungTableModel() {
}
HashMap prims=new HashMap();
/**
* Tested ob n eine Primzahl ist
* @param n int
* @return boolean
*/
public boolean isPrim(int n) {
BigInteger bla = new BigInteger(new Integer(n).toString());
return bla.isProbablePrime(10);
}
/**
* Gebe die n te Primzahl zurück
* @param n int
* @return int
*/
public int getNprim(int n) {
if(prims.containsKey(new Integer(n))){
return ((Integer)prims.get(new Integer(n))).intValue();
}
int i = 0; // Nummer der Primzahl
int a = 0; // Zahl, die auf Primzahl getestet wird
while (i < n) {
a++;
if (isPrim(a)) {
i++;
prims.put(new Integer(i),new Integer(a));
}
}
return a;
}
/**
* Wie oft steckt prim in i?
* @param prim int
* @param i int
* @return int
*/
public int getPriminI(int prim,int i){
int a=i;
int count=0;
while(a%prim==0){
a= a / prim;
count++;
if(a==0)break;
}
return count;
}
public int getRowCount() {
return 10000000;
}
public int getColumnCount() {
return 100;
}
public Object getValueAt(int rowIndex, int columnIndex) {
if(columnIndex==0){
if(this.isPrim(rowIndex)){
return rowIndex+"-";
Sven Köhler
Primfaktorzerlegung läuft auch unter dem Namen Faktorisierung. Wenn es
dafür einen schnellen Algorithmus gäbe, dann hättest alle
Kryptoverfahren wie RSA usw. geknackt.
Paul Ebermann
> Es gibt deterministische Primzahltests, die glaube ich in O(n^12) oder
> O(n^6) laufen, aber die sind damit häufig noch um ein vielfaches
> langsamer als der Rabin-Miller-Algorithmus, der wirklich relativ gut
> ist.
Achtung: Das n ist hier nicht etwa die zu prüfende Zahl
(da würde ich einen schnelleren Algo kennen ...), sondern
deren Länge (z.B. in Bits).
Paul
Marco Lange
Ja, wie in der Komplexitätstheorie üblich wird die Länge der Eingabe
betrachtet. Wobei dies auch nicht wirklich klar definierter Begriff ist.
Man kann jede Natürliche Zahl auch unär kodieren in dem man der Zahl k
die Folge 1^k zuordnet, also eine Folge von k Einsen.
Im allgemeinen verwendet man aber "sinnvolle" Kodierungen wie etwa die
binäre Kodierung.
Viele Grüße,
Marco
Michael Borgwardt
Es gibt durchaus asymmetrische Verschlüsselungsalgorithmen die nicht mit
einer Primfaktorzerlegung zu knacken sind (bei symmetrischen spielt das
sowieso keine Rolle).
Martin Demberger
ich bin selbst ein großer Fan von Primzahlberechnungen. Auf die Zerlegung
habe ich noch nicht viele Gedanken verloren, jedoch auf die Berechnung. Und
damit auf die isPrim(int n)-Methode.
Schau dir doch mal die folgende Klasse an:
package vu.de.demberger.tools.math;
import java.util.NoSuchElementException;
/**
* @author M. Demberger - Demberge...@gmx.de
* @version 1.0 (16.06.2004)
* @since 16.06.2004
*/
public final class Prim {
private static final int INITAL_SIZE = 10000;
private static final class Primary {
public final int primary;
public int times;
public final Integer obj;
public Primary(int primary) {
this.primary = times = primary;
obj = new Integer(primary);
}
}
private Primary[] primaries;
private int step;
private int size;
private int current;
public static Prim getIntance() {
return new Prim();/** @todo Implementieren */
}
private Prim() {
primaries = new Primary[INITAL_SIZE];
primaries[0] = new Primary(2);
primaries[1] = new Primary(3);
step = 4;
current = 1;
size = 2;
}
private void createNext() {
boolean isPrim = false;
while (!isPrim) {
current += step;
step = 6 - step;
isPrim = true;
for (int i = 2; i < size; i++) {
Primary p = primaries[i];
while (p.times < current) p.times += p.primary;
if (p.times == current) {
isPrim = false;
}
}
if (isPrim) {
if (size >= primaries.length) {
Primary[] p= new Primary[primaries.length * 2];
System.arraycopy(primaries, 0, p, 0, primaries.length);
primaries = p;
}
primaries[size++]= new Primary((current));
return;
}
}
}
private Primary getPrimary(int idx) {
if (idx < 0) {
throw new NoSuchElementException();
} else {
while (idx >= size)
createNext();
return primaries[idx];
}
}
public int get(int idx) {
Primary p = getPrimary(idx);
return p.primary;
}
public Integer getInteger(int idx) {
Primary p = getPrimary(idx);
return p.obj;
}
public boolean isPrim(int i) {
int idx = 0;
int p;
do {
p = get(idx++);
} while (p < i);
return p== i;
}
public boolean isPrim(Integer i) {
return isPrim(i.intValue());
}
}
Für Dokumentation habe ich bisher noch keine Zeit gehabt. Die Idee die
dahinter steckt ist nicht von mir sondern von einem Prof. einer Wiener Uni.
(Ich will mich nicht mit fremden Lorbeeren schmücken) Ich weis aber nicht
von welchem da ich nur den Ausdruck des Quellcodes bekommen habe mit der
Info "Der ist von der Uni Wien".
Falls dir ein Fehler auffällt oder du eine Verbesserung weist dann gib mir
bitte bescheid.
cu Martin
Matthias Treydte
> oder du eine Verbesserung weist dann gib mir bitte bescheid.
Die Sache mit dem Primzahltest ist in polynomieller Laufzeit möglich,
siehe: http://www.cse.iitk.ac.in/news/primality.html
MfG,
Matthias
--
You can't make it foolproof, the fools are too inventive.
Carsten Hammer
vielen Dank für den Tip, muss ich mir noch anschauen. Ein kurzes
Einfügen in mein Programm brachte die Antwortzeiten zum Erliegen, aber
das ist wohl auch nicht anders zu erwarten gewesen, wenn man *richtig*
prüft.
Unter http://home.t-online.de/home/carsten.hammer/primfaktortest.html
kannst Du sehen, wie die Primfaktorzerlegungen der ersten 100 Millionen
Ganzzahlen aussehen (allerdings nur die Anteile der ersten 500
Primzahlen darin). Wenn ich da Dein Programm für die Verifizierung auf
Primzahl oder nicht aufrufe, dann ist das leider nicht mehr benutzbar
sobald die Zahlen grösser werden (Ich hoffe ich habe alles richtig
gemacht). Vielleicht lässt sich das ja irgendwie in einen workerthread
legen und nur bei problematischen Zahlen aufrufen oder so.
Tschö,
Carsten
Martin Demberger schrieb:
Paul Ebermann
> > oder du eine Verbesserung weist dann gib mir bitte bescheid.
>
> Die Sache mit dem Primzahltest ist in polynomieller Laufzeit möglich,
> siehe: http://www.cse.iitk.ac.in/news/primality.html
Ich wage zu behaupten, dass das im int-Bereich trotzdem nicht
schneller ist als die Methode von Martin - erst recht, wenn
es darum geht, eine ganze Reihe von Primzahlen bzw. die n-te
Primzahl zu berechnen.
Paul
Matthias Treydte
> Ich wage zu behaupten, dass das im int-Bereich trotzdem nicht
> schneller ist als die Methode von Martin
Stimmt. Aber es gibt ja auch ne Menge Primzahlen > Integer.MAX_VALUE,
irgendwann lohnt sich's. :-)
ciao,
Paul Ebermann
> > Ich wage zu behaupten, dass das im int-Bereich trotzdem nicht
> > schneller ist als die Methode von Martin
>
> Stimmt. Aber es gibt ja auch ne Menge Primzahlen > Integer.MAX_VALUE,
> irgendwann lohnt sich's. :-)
Da muss er aber sein ganzes Programm umschreiben, um mit
BigInteger o.ä. zu arbeiten.
Paul
Martin Demberger
meine erste Klasse war auf das Berechnen von Primzahlen optimiert. Nicht
auf das zerlegen. Ich habe jetzt mal noch eine geschrieben die Primzahlen
durch die Multiplikation erzeugt. Als "Nebenprodukt" werden dabei die
Primfaktoren erzeugt. Dieser Berechnungsansatz kommt eher aus der
funktionalen Programmierung und nicht aus dem OOP.
Falls die Berechnung nicht schnell genug ist, dann liegt es mit ziemlicher
Sicherheit an zwei verschiedenen Sachen. Zum Einen werden Werte weit im
Voraus berechnet, mit ein bisschen überlegen müsste das schnell behoben
sein. Zum anderen wird viel Speicher erzeugt und freigegeben. Durch eine
eigene Speicherung der Werte als echten int und ohne Set oder Map kann da
mit Sicherheit viel gewonnen werden.
cu Martin
--------------------------------------------------------------------
package vu.de.demberger.tools.math;
import java.util.*;
/**
* @author M. Demberger - Demberge...@gmx.de
* @version 1.0 (24.08.2004)
* @todo Dokumentieren
* @todo Testen
* @since 24.08.2004
*/
public class PrimFactorMap implements Map {
private Map values = new HashMap();
private int lastValue = 1;
private Set prim = new HashSet();
public static class Entry implements Map.Entry {
private Integer value;
private List prims;
Entry(Integer value, List prims) {
this.value = value;
this.prims = prims;
}
public Object getKey() {
return value;
}
public Object getValue() {
return prims;
}
public Object setValue(Object value) {
throw new UnsupportedOperationException();
}
}
public int size() {
return values.size(); /** @todo Implementieren */
}
public boolean isEmpty() {
return false;
}
public boolean containsKey(Object key) {
return key instanceof Integer;
}
public boolean containsValue(Object value) {
throw new UnsupportedOperationException("Noch nicht
implementiert");
}
public Object get(Object key) {
int nr = ((Integer)key).intValue();
while (lastValue < nr) {
lastValue++;
Integer i = new Integer(lastValue);
List l = (List)values.get(i);
if (l == null) {
l = new ArrayList();
l.add(i);
values.put(i, l);
prim.add(i);
}
Iterator it = prim.iterator();
while (it.hasNext()) {
Integer p = (Integer)it.next();
List tmp = new ArrayList(l);
tmp.add(p);
values.put(new Integer(lastValue * p.intValue()), tmp);
}
}
return values.get(key);
}
public Object put(Object key, Object value) {
throw new UnsupportedOperationException();
}
public Object remove(Object key) {
throw new UnsupportedOperationException();
}
public void putAll(Map t) {
throw new UnsupportedOperationException();
}
public void clear() {
throw new UnsupportedOperationException();
}
public Set keySet() {
return values.keySet();
}
public Collection values() {
return values.values();
}
public Set entrySet() {
return values.entrySet();
Bernd Eckenfels
> Durch eine
> eigene Speicherung der Werte als echten int und ohne Set oder Map kann da
> mit Sicherheit viel gewonnen werden.
Diese Spielchen dürften im Integer bereich aber ziemlich nutzlos sein. Eine
Sieb Implementierung ist auf jeden Fall nicht geeignet große Zahlen
"schnell" zu faktorieren.
Gruss
Bernd
--
eckes privat - http://www.eckes.org/
Project Freefire - http://www.freefire.org/
Martin Demberger
> Martin Demberger <Mart...@gmx.de> wrote:
>> Durch eine
>> eigene Speicherung der Werte als echten int und ohne Set oder Map kann da
>> mit Sicherheit viel gewonnen werden.
>
> Diese Spielchen dürften im Integer bereich aber ziemlich nutzlos sein. Eine
> Sieb Implementierung ist auf jeden Fall nicht geeignet große Zahlen
> "schnell" zu faktorieren.
Stimmt, schnell ist es eigentlich nur, wenn man der Reihe nach die
Primfaktoren will. Und aufgrund der Beispielanwendung von Carsten habe ich
das vermutet. Wobei mir inzwischen auch gekommen ist meine Lösung auch in
diesem nicht allzu sinnvoll ist. Denn dann müsste man Zeile für Zeile
scrollen und nicht innerhalb der Tabelle Springen...
cu Martin