Thread: Primzahlengenerator

hmm ich find egerade irgendwie nicht woher die Variable ul kommt   
aber ich glaube du machst das zu kompliziert   
http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

ist eine sehr bekannt Methode...
wenn ich das richtig sehe, dann prüfst du ja jede Zahl...
entschuldige bitte, wenn ich mich vertan haben sollte   

habe von C++ nicht so die Ahnung^^ da wäre ich bei Delphi besser aufgehoben, wobei ja Delphi so die beginner Sprach eist^^

LG

Hi, ich mache grade in Bremen an der Jacobs Uni einen kleinen Kurs zum Thema Kryptographie, zu dem unter anderem natürlich auch die Suche nach Primzahlen gehört. Grade heute habe ich dort den Fermat-Test kennen gelernt.

Dieser besagt:
Ist n eine Primzahl, so gilt für alle b mit gcd(b,n) = 1:
b^(n-1) [kongruent] (mod n)

Gilt c ![kongruent] 1, so ist n keine Primzahl.

"![kongruent]" bedeutet nicht kongruent (hab das richtige Zeichen nicht gefunden)

Die Wahrscheinlichkeit des ersten Teil beträgt nur 50%. Du kannst sie jedoch erhöhen, wenn du den Test öfters mit anderen 1 < b > n aus den Natürlichen Zahlen durchführst.
Also nach dem zweiten Test 75% nach dem dritten 87,5% usw.

Mehr Informationen findest du bei Wikipedia. Notfalls helfe ich dir auch noch. (Komme aber erst spät nach Hause)

Ich hoffe, dass dir die Methode hilft. Du bekommst zwar nie eine 100%ige Sicherheit, allerdings reichen vielleicht auch schon 99,99%, die man im Vergleich des "Schleife schreiben und durchlaufen lassen" bei hohen Zahlen schneller erreichen kann.

J-C

Edit: Er mag leider auch mein kongruent-Symbol nicht. Ich schreibe stattdessen "[kongruent]".

ul ist gar keine Variable :P. Das ul bedeutet, dass die Zahl die davor steht unsigned long ist. Wenn ich das ul weglasse ist nicht fest welchen Typ die Zahl hat, so könnte es short oder signed sein. Das würde bedeuten, dass er erst mal jedes mal eine Typumwandlung durchführen müsste, nimmt sicher nicht viel weg, aber ist in dem Fall auch unnötig, sofern der Compiler das nicht optimiert und sowieso als unsigned long im Programm abspeichert.


Naja wie du schon sagtest prüfe ich (fast) jede Zahl, einfacher gehts ja wohl nicht :P. Aber das eine Verfahren von dir leuchtet mir ein und dürfte noch deutlicher flotter gehen, was die CPU angeht. Jedoch wäre der Speicherverbrauch bei großen Bereichen enorm, ausserdem müsste man immer bei 2 beginnen oder alternativ müsste man jede Zahl Prüfen die noch als Primzahl gekennzeichnet ist. Was bei einer hohen Anfangszahl und einem Bereich der kleiner als die Anfangszahl sogar bedeuten könnte, dass er JEDE Zahl prüfen muss! (Was in dem Fall deutlich langsamer wäre).

Naja das verstehe ich einerseits nicht ganz und andererseits könnte es sein, dass diese Methode falsche Primzahlen liefert? Denn ich wollte keine Annährung an richtige Primzahlenfolgen, sondern eben richtige Primzahlenfolgen ohne falsche Primzahlen.

Ich hätte nicht gedacht, dass sich in dem Thread so viele Leute melden. Eigentlich sollte das Programm ursprünglich auch nur zur CPU Auslastung dienen :).

Aber eine Frage hätte ich noch in wie fern kann man Primzahlen in der Kryptographie gebrauchen?

Die Wahrscheinlichkeit, dass man eine Zahl bekommt, nachdem man diese Rechenschritte 8 mal durchgeführt hat, liegt bei 0,390625%. Und wenn man einfach nochmal 8 drauflegt, hat man diese auf 0,001526% verringert.
Es ist jedoch deine Sache, ob du diesen Test benutzen willst. Wenn es nur eine CPU-Auslastung werden soll, solltest du einfach nur alle Zahlen durchtesten ohne dem Trick mit der Wurzel und ohne diesem Test.
Wenn es allerdings wirklich Primzahlen finden soll, musst du dich nach besseren Alogrithmen umsehen (effizientere und sichere). Mit dem Fermat-Test wärst du allerdings schonmal auf dem richtigen Weg.



Praktisch alle heute benutzten Arten der Kryptographie benötigen Primzahlen zur verschlüsselung, da diese nicht so einfach in ihre Faktoren zu zerlegen sind.

Im Moment werden praktisch alle Arten von Verschlüsselung durch RSA verschlüsselt. Hierfür benötigt man 2 verschiedene Primzahlen, die in ein bestimmtes Schema passen.
Zum Beispiel die Verschlüsselung von SSL-Verbindungen (u.a. https) wird mit RSA durchgeführt.

Edit: Wirklich neue Primzahlen wirst du auf diesen Wegen allerdings nicht finde... Dafür bräuchte man einfach zu viel Rechenleistung, als dass man das auf normalen Desktops lösen könnte. Da muss man dann schon etwas größeres benutzen.


J-C

Das kannst aber deutlich einfacher haben   und wenn jetzt noch ein multi core system hast startest davon einfach ein paar Threads ;)

btw: finds eigentlich ganz cool, wenn sich mal jemand mit Algotithmen auseinandersetzt :)

So, ich habe mal das kleine Prog von damals umgeschrieben und diesmal nutzt es das Sieb des Eratosthenes zur Berechnung.

Es ist zwar ultraschnell aber nur so lange der RAM reicht und es ist ziemlich speicherhungrig. So hatte ich bei einer drittel Milliarde Zahlen eine Speicherauslastung von über 1GB und bei einer halben Milliarde waren das schon ca. 2 Gigabyte was bei mir nicht mehr flüssig berechnet werden konnte, da ich nur 2GB RAM habe und Windows so alles (nicht nur einen Teil) auf die Festplatte auslagern musste.

Für eine drittel Milliarde (333.333.333) habe ich 32.468 Sekunden gebraucht, beim alten Prog dauert das sicher Tage.

Beide Progs kann man sich auf der Seite des 1. Posts runterladen, samt Quellcode und ausführbaren Dateien für Windows und Linux (beides 32bit).

Kommt vermutlich stark darauf an, wie du die Daten speicherst.

Im Prinzip kann man zwei Phasen unterscheiden:

• Anfangsphase: Viele Einträge, es wird stark gesiebt
• Endphase: Wenig Einträge, es wird wenig gesiebt

Wie speicherst du die Daten denn? Array, verkettete Liste?

Ein einfaches Array dass ich dynamisch erstelle je nach dem wie viel Speicher benötigt wird. Die größe bleibt jedoch bis zur Aussgabe erhalten und wird nicht verändert, nicht Primzahlen werden mit einer 0 überschrieben. Mir ist klar, dass ich es im laufe des Programmes zwar verkleinern könnte, aber das könnte das Programm unter Umständen sogar verlangsamen.

Denn das Problem besteht eben darin, dass ich bei einem normalen Array nicht einfach Elemente rauslöschen kann, ich müsste immer erst einen neuen fast genauso großen Speicherbereich anfordern und dann alles rüberkopieren, bis auf das was rausfliegt. Zwar könnte ich vorher die Werte nach vorne schieben und dann realloc nutzen um das Array zu verkleinern aber wenn mans genau nimmt würde das noch weniger bringen, denn realloc verkleinert nicht einfach den Speicher meines Wissens sondern sucht einen neuen passenden Bereich und kopiert das in diesen neuen Bereich und gibt anschliessend den alten frei.
Solange man also noch im RAM arbeitet dürfte das deutlich langsamer sein und wenn es auslagert denke ich auch nicht, dass die Festplatte das schneller kann es würde einzig schnell werden wenn das Array dann klein genug geworden ist, die Frage ist nur ob die Zeit die dann später eingespart wird größer ist als die, die man für das ständige verändern des Arrays verschwendet. Ausserdem würde man 2 mal so viel Speicher brauchen um den Speicher überhaupt verkleinern zu können.

Das mit den verketteten Listen wäre auch eine Möglichkeit wo sogar die Möglichkeit besteht mittendrin Elemente rauszulöschen. Jedoch hat diese Methode 2 andere Nachteile sie ist 1. rechenintensiver (das ständige Ablaufen der Liste zum Beispiel) und 2. noch speicherhungriger (um genau zu sein, doppelt so viel, wenn nicht gar mehr, denn auch ein Zeiger verbraucht Speicher)! Gegen Ende dürfte die Methode aber wahrscheinlich recht flott sein.

Ob dann wirklich eine der anderen beiden Varianten schneller ist weis ich nicht, wenn dann womöglich eher die 2.

Edit: Hmm da stellt sich mir die frage wird das mit dem neuen Bereich anfordern eigentlich nur durchgeführt wenn der Speicher vergrößert wird (was hier nicht der Fall ist), wenn dahinter gar kein Platz ist oder immer?

Um den Speicher etwas einzudämmen, könntest du folgendes machen: Anstatt Zahlen in einem Array zu speichern, kannst du mit booleaschen Werten arbeiten. Wobei dann der Index deine Primzahl ist. Befindet sich bei dem speziellen Index eine Primzahl schreibst du einfach true rein, ist dort keine schreibst du false rein.

Funktioniert gut, ich habe das damals so in PHP gemacht. im ganzen nicht mehr als zehn Zeilen, also eine sehr einfach zu programmierende Lösung. (In C++ etwas auffwändiger.)

Es geht aber noch speicherfreundlicher und zwar indem du anstatt booleaschen Werten einfach mit Flags arbeitest. Wenn du z.B. ein Byte-Array machst, liefert dir ein jedes Byte 8 "Speicherplätze" für deine Primzahlen. Die einzige Zahl die dann wirklich groß wird, wäre der Counter der sie alle durchläuft.

Das würde, glaub ich, einiges an Speicher sparen. Natürlich ist das nur ein zusätzlicher Speicher-Tuningkniff aber er sollte helfen.

Stimmt das könnte ich noch machen, was mir auch aufgefallen ist, dass ich wieder alle Werte durchprobiere, jedoch könnte ich auch hier bei wurzel aus max eigentlich aufhören.