Was haltet ihr von diesem Primzahl Algorithmus

Neue Frage »

Matthias Redies Auf diesen Beitrag antworten »
Was haltet ihr von diesem Primzahl Algorithmus
Hallo,
ich habe mich mal ein wenig mit dem finden von Primzahlen beschäftigt. Ich habe eine Methode entwickelt, wie man das Suchen von großen Primzahlen auf ein Cluster verteilen kann. Bisher habe ich keine ähnlichen Ideen gesehen, falls es die doch schon gibt bitte ich um Entschuldigung.

Ich hab den Algorithmus in einer kleinen Arbeit vorgestellt. Es wäre nett, wenn ich euch das mal durchlest und mir ein paar Rückmeldungen/Verbesserungsvorschläge gebt. Ich weiß nicht ob sowas hier hingehört, aber ArXiv ist ja nur auf Empfehlung Augenzwinkern

Es folgt noch der kommentierte Quellcode(hier mit Syntax-Highlighting):
Wer das komplette Programm runterlanden will tut das hier. Der Server muss allerdings immer entsprechend geändert werden.
Clients:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
package primzahl_client;

import java.net.*;
import java.io.*;

// @author Matthias Redies

public class Main {

    private static PrimList zahlen = new PrimList();

    //Fügt eine neue Primzahl in die lokale Liste des Clients ein
    public static void add_prim(int n){
        zahlen.append(new Zahl(n));
    }
    //überprüft ob in der lokalen Liste Teiler sind
    public static boolean test_prim(int n){
        zahlen.goto_first();
        while(zahlen.get_number()*zahlen.get_number() <= n){
            if(n % zahlen.get_number() == 0){
                return false;
            }
            zahlen.goto_next();
        }
        return true;
    }



    public static void main(String[] args) throws IOException {
        //Server bitte hier eintragen:
        Socket server = new Socket("192.168.1.101",1234);

        InputStream input = server.getInputStream();
        OutputStream output = server.getOutputStream();
        
        //Endlosschleife
        while(true){
            /* als erstes wird ein String eingelesen, der übermittel, was
             * nächstes übermittelt wird.
             */
            byte[] c = new byte[10]; 

            input.read(c);
            String nachricht = new String(c);
            DataInputStream in = new DataInputStream(input);
            DataOutputStream out = new DataOutputStream(output);
            if(nachricht.equals( "next: Prim")){
                int prim = in.readInt();
                add_prim(prim);
            }else if(nachricht.equals("next: Zahl")){
                int zahl = in.readInt();
                out.writeBoolean(test_prim(zahl));
                out.flush();

            }
        }       
    }
}


code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
package primzahl_client;
/**
 * @author Matthias Redies
 */
public class PrimList {
    private Zahl first = null;
    private Zahl aktuell = null;

    public boolean is_empty(){
        return first == null;
    }

    public int get_number(){
        if(aktuell != null){
            return aktuell.get_number();
        }else{
            return 0;
        }
    }

    public int size_of(){
        if(! is_empty()){
            int i = 1;
            goto_first();
            while(aktuell.get_next() != null){
                i++;
                goto_next();
            }
            return i;
        }else{
            return 0;
        }
    }

    public void goto_first(){
        aktuell = first;
    }

    public void goto_next(){
        if(aktuell != null){
            aktuell = aktuell.get_next();
        }
    }

    public void goto_last(){
        while(aktuell.get_next() != null){
            goto_next();
        }
    }

    public void append(Zahl n){
        if(first == null){
            first = n;
            goto_first();
        }else{
            goto_last();
            aktuell.set_next(n);
            goto_next();
        }
    }

}
Math1986 Auf diesen Beitrag antworten »

Wie sieht denn die Klasse Zahl aus?
kiste Auf diesen Beitrag antworten »

Ist ganz nett als Forschungsprojekt in der Mittelstufe oder sowas, aber weiter wirst du mit der Idee kaum kommen Augenzwinkern
Aber vom Ansatz her ist das natürlich genau das was auch gemacht wird(wobei ich nicht wüsste warum man alle Primzahl <= n haben möchte).

Für einen Primzahltest ist es natürlich nicht geeignet.
Matthias Redies Auf diesen Beitrag antworten »

Zitat:
Original von Math1986
Wie sieht denn die Klasse Zahl aus?

Zahl ist eine einfach verkette Liste(im Grunde ein wachsendes Array) mit Integerzahlen.

Zum Primzahltest: Das Prinzip ließe sich ein wenig erweitern, dann müsste man auch Faktorisierungen oder Primzahltests auf einem Cluster ausführen können.

Der große Vorteil, nämlich das verteilte Rechnen, kommt erst bei sehr großen Zahlen zum Tragen. Vorher wird leider enorm viel Zeit für die Kommunikation verbraucht
sulo Auf diesen Beitrag antworten »

Du solltest noch mal die Grammatik und Rechtschreibung deines Textes prüfen. Augenzwinkern
Cugu Auf diesen Beitrag antworten »

Zitat:
Zum Primzahltest: Das Prinzip ließe sich ein wenig erweitern, dann müsste man auch Faktorisierungen oder Primzahltests auf einem Cluster ausführen können.

Ja, richtig, das ist möglich. Wenn wieder einmal empfohlen wird, längere RSA-Schlüssel zu verwenden, weißt du, das das gerade jemand erfolgreich umgesetzt hat (so wie Anfang des Jahres in Bonn). Die Algorithmen waren allerdings effizienter...
 
 
Matthias Redies Auf diesen Beitrag antworten »

Zitat:
Original von Cugu
Zitat:
Zum Primzahltest: Das Prinzip ließe sich ein wenig erweitern, dann müsste man auch Faktorisierungen oder Primzahltests auf einem Cluster ausführen können.

Ja, richtig, das ist möglich. Wenn wieder einmal empfohlen wird, längere RSA-Schlüssel zu verwenden, weißt du, das das gerade jemand erfolgreich umgesetzt hat (so wie Anfang des Jahres in Bonn). Die Algorithmen waren allerdings effizienter...


Ich habe auch gelesen das die empfohlene Schlüssellänge vergrößert wurde, aber da stand nichts zu dem der den Schlüssel geknackt hat. Hast du zufälligerweise einen Link parat?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »