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 :)