@Omikron2
Wenn Du dir die geposteten Algorithmen ansiehst, wirds Du merken, dass a) nut bis zur Wurzel der zutestenden Zahl geprüft wird, Und als mögliche Teiler werden zuvor gefundene Primzahlen verwendet(Sieb des Namenvergessen), was wieder eine Geschwindigkeitserhöhung gibt.

Durch Googeln habe ich folgende Funktion gefunden:
p ist prim -> (2^p)-1 auch prim

2 -> 3
3 -> 7 >> und 5?
7 -> 127 >> hier fehlen noch mehr.

Du siehst, die Funktion f(x)=(2^x)-1 erzeugt zwar Primzahlen aber leider fehlen etliche Primzahlen. Diese Funktion dient nur zum Beweiss das es unendlich viele gibt. Und ich bin mir sicher, das es diese Funktion auch schon vor 2002 existent war.

@Tilo Das kann ich mir nicht so ganz vorstellen. Wenn gelten würde:

p ist prim -> (2^p)-1 auch prim

Dann wäre es doch extrem einfach, eine größere Primzahl als die bisher größte bekannte Primzahl zu finden oder nicht? Wenn jetzt z.B. die Zahl 4527835 die größte bekannte Primzahl wäre (hab jetzt net geguckt obs überhaupt eine ist ), dann wüsste man doch auch, dass 2^4527835-1 auch eine Primzahl wäre, und somit hätte man eine viel größere gefunden.

Oder hab ich da jetzt was falsch aufgefasst?


Ich Bins

(2^p)-1

gilt nicht als beweis für primzahlen...
die wahrscheinlichkeit das die zahl eine primzahl ist, ist nur wesentlich größer als wenn man irgend eine andere zahl nimmt

Sorry, aber diese Funktion habe ich auf einer UNI-Forum Seite gefunden.

Hallo!

Wenn ihr richtig große Primzahlen finden wollt, lest euch das mal durch:

Zitat:

Der kleine Fermatische Satz: Ist p eine Primzahl und b eine zusammengesetzte Zahl, so ist b^p-b ein Vielfaches von p. Wenn p=7 und b=2: 2^7-2=126.Dann kann man 126/7 teilen. 1979 wurde bewiesen, daß 2^44497-1 eine Primzahl ist. So können wir darauf schließen, daß 3^2^44497-1) -3/ 2^44497-1 ohne Rest teilbar ist. B^p-b/p ( da kommt Rest 0 heraus) 2^11-2=2046/11 Der Rest ist aber ungleich null und damit ist die Ausgangszahl zusammengesetzt!!! Pseudoprimzahlen: 2^341-2 ist ein Vielfaches von 341, obwohl 341 eine aus dem Produkt von 11 und 31 zusammengesetzte Zahl ist. Deswegen sind bei der Divisionsmethode Einsparungen zu machen, da es auf den Rest ankommt. Hier kommt die Arithmetik der Kongruenz ins Spiel. 3^1037-3 ist durch 1037 kongruent zu 845 modulo 1037.(Daß heißt, daß die erste Zahl bei der Division durch 1037 die zweite Zahl als Rest liefert. Also kann der Rest bei /1037 nicht null sein, da 1037 zusammengesetzt ist. Jedoch tritt das Problem der Pseudoprimzahlen eher selten auf. Es existieren unterhalb 10^10 455052512 Primzahlen. Zu b=2 gibt es nur 14884 Pseudoprimzahlen, wobei 561 die kleinste ist. Weil der Fermatische Test so gut funktioniert wurde er versucht zu verbessern, daß die Pseudoprimzahlen wegfallen. Man will mehr über zusammengesetzte Zahlen erfahren, damit man herausbekommt auf welche Weise sie sich tarnen. Diese Tests liefern Informationen über getestete Zahlen und nicht nur ob sie „bestanden“ haben oder „durchgefallen“ sind. Diese Ergebnisse ähneln einem Mosaik, wobei die Informationen über die Zahl auf die einzelnen Steinchen verteilt ist. So können wir an Hand dieses Mosaiks sehen, ob es Primzahlen sind. Anfangs der 80 er Jahre wurden effiziente Tests zum Algorythmus gemacht. Len Adleman, Robert Rumely und Carl Pomerance haben dazu beigetragen. Die Abwandlung davon schuf Hendrik Lenstra und beschleunigte die Arbeit. Die Informatik fragt sich, ob man diese Arbeit noch beschleunigen kann. Dafür ist die Komplexitätstheorie verantwortlich. Sie klassifiziert die Beispiele in einfach und schwierig. Wieviel Zeit braucht der Computer? Nimmt die Zahl der Rechenschritte mit der Funktion k*n^q zu, wobei q und k feste bestimmte Zahlen sind. Kann man dies in polynomialer Zeit schaffen? (einfach) K*q^n ist nicht in polynomialer Zeit zu schaffen. Deswegen ist es schwierig.

(Ich hoffe, ich hab ein richtiges Zitat....)

Man kann über sehr große Zaheln sehr "schnell" sagen, ob es nicht prim ist.
Leider kann man dann nur sagen, das eine Zahl sehr wahrscheinlich Prim ist.....
Dies wird für die heutigen, gängigen Verschlüßelungen ausgenutzt, die sehr große Primzahlen erfordern. (asymetrische Verschlüßelung, vor allem RSA)

Die Methode: Man nimmt eine beliebige Zahl, die zu prüfen ist (p).
Man geht mit einer Reihe Zahlen (a) mit einer Formel durch. Ist die Gleichung auch nur einmal nicht erfüllt, ist die Zahl 100% nicht prim. Man kann so die Wahrscheinlichkeit, eine Primzahl gefunden zu haben, stark erhöhen, in dem man mit vielen Zahlen testet. Die Formel hab ich im moment nicht griffbereit, aber es war irgendwas mit potenzen in der Modoloebene (erfordert schon einen eigenen Algorythmus *g*) Müsst mal suchen...
Damit hab ich mal 100-Stellig Pseudoprimzahlen in wenigen Minuten finden können (Ihr braucht aber auch sowas wie THugeInt, ich glaub, das istz aber bei D7 schon mit dabei....)

Also, viel Spaß beim Suchen...

Moderiert von AXMD: BB-Codec aktiviert

Omikron2 hat folgendes geschrieben:

Es gibt seit 2002 glaube ich einen algorithmus der zahlen auf prim überprüft und nur einen linearen rechenaufwand hat (es müssen nicht mehr alle möglichkeiten ausprobiert werden) googlen hilft vielleicht! mfg

Stimmt schon, da gibts ein Algo.... dummerweise ist der für Quantencomputer Du kannst zwar auf einen normalen PC einen Quantencomputer simullieren (und andersrum), dummerweise steigt die Rechenzeit dann wieder quadratrisch an^^

F34r0fTh3D4rk hat folgendes geschrieben:

... Ich habe gehört, dass es eine Belohnung geben soll, wenn man eine 100 Stellige Primzahl findet, also ranhalten jungs !!!

100 nicht ganz... 10 Millionen stellen Die größte bekannte Primzahl bis dato (225,964,951-1) hat "nur" 7,8Mio. Stellen. hier ist ein Link. Lest sie, lernt sie, lebt sie . Ein paar allgemeine Infos findet ihr hier: www.mersenne.org/prime.htm

MfG Zemy

Sorry wenn ich jetzt was doppelt poste aber hab die mittleren Seiten nicht gelesen.

Das Program Prime 95 vom Primzahlprojekt Gimps nutzt zur Primzahlberechnung Lucas-Lehmer iterations. Kenne diese zwar nicht, scheint aber der professionellste Ansatz für dieses Problem zu sein.

Das Prog läuft grad bei mir und rechnet ^^

www.devalco.de/mersenne.htm

Tilo: (2^x)-1 ist natürlich nicht garantiert Prim und es dient auch nicht als Beweis, dass es unendlich viele Primzahlen gibt.
Man denke an 255 oder 65535. Die sind wie alle anderen Zahlen, die mit 5 enden, nicht Prim (ausser die 5 selbst).

Aber ich habe wieder ein seite gefunden die (2^p)-1 als Prim ansieht, wenn p eine Primzahgl ist!

Tilo hat folgendes geschrieben:

Aber ich habe wieder ein seite gefunden die (2^p)-1 als Prim ansieht, wenn p eine Primzahgl ist!

Die Klammersetzung ist falsch: 2^(p-1) mod p == 1
Gilt aber nur als Pseudo-Primalitätstest ...
Gibt noch einen Rabbin-Miller-Test, der den Exponenten p-1 = s * 2 ^ k darstellt und auch 2^s mod p == 1 überprüft.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Kleiner Einschub, da hier aufkam, warum es unendlich viele Primzahlen gibt: Das ist ganz einfach zu sehen - durch einen Widerspruchsbeweis:

Angenommen, es gäbe nur endlich viele Primzahlen - nennen wir diese endlich vielen Primzahlen p_1,p_2,p_3,...,p_n. Dann bilden wir daraus eine neue Zahl, nämlich das Produkt aller Primzahlen, und addieren 1 hinzu: X=(p_1 * p_2 *...*p_n) +1. Jetzt kann man sich leicht überlegen, das X durch keine der Primzahlen teilbar sein kann, also wäre X auch eine Primzahl. Das steht aber im Widerspruch dazu, dass wir bereits alle Primzahlen gefunden haben. Also gibt es unendlich viele.

Hinweis: da es nicht nur die Primzahlen p_1 bis p_n gibt, ist X auch nicht notwendigerweise wirklich eine Primzahl. Auf diese Weise kann man also auch nicht einfach große Primzahlen finden.

Also ich habe diese Diskussion verfolgt, weil ich genau das gleiche Prob habe, konnte aber teilweise nur begrenzt folgen. Ich frag deshalb einfach nochmal direkt nach: Mittels welchem Algo finde ich Primzahlen, in meinem Fall mit ungefähr 30 Stellen?

Rabbin-Miller-Test, indem Du für 10 bis 20 verschiedene Primzahl-Basen die Starke Pseudo-Primalität prüfst ...

d.h.

Generierung einer 30*ld(10)=99,6 bit-->100 bit breiten Zufallszahl
Setzen von Bit 0
Setzen von Bit 99
Durchführung des SPS-Tests* für die Basen 2,3,5,7,11,13,7,19,23,...
Wenn die Zahl in einem dieser Tests durchfällt, ist sie nicht prim, fortsetzen mit Schritt 1

*SPS-Test:
Z' = Z - 1
S = Anzahl der bei Z' niederwertigen 0-Bits (bei 40 wären dies 3 [101000])
Z'' = Z' / 2^S
For N = 0 TO S DO
Basis ^ (Z'' * 2 ^ S) MOD Z == 1;

Ist diese Gleichung für eine Zahl nicht erfüllt, dann ist Z nicht Stark Pseudo-Prim zur Basis B.

Damit solltest Du eigentlich recht gute Ergebnisse von der Geschwindigkeit erzielen ...

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Würde man aber alles auf ca. 30 Primzahlen begrenzen. Wenn es notfalls auch ne Pseudoprimzahl sein kann, einfach ne Zufallszahl in dieser größenordnung generieren und dann durchprobieren, bis ein Pseudoprimtest Ja sagt. Kannst dann auch einen richtigen nachschieben um sicherzugehen (Teiler suchen von 2 bis Wurzel Zahl).

BenBE hat folgendes geschrieben:

Z'' = Z' / 2^S For N = 0 TO S DO Basis ^ (Z'' * 2 ^ S) MOD Z == 1; Ist diese Gleichung für eine Zahl nicht erfüllt, dann ist Z nicht Stark Pseudo-Prim zur Basis B. ...

Da frage ich doch noch einmal dumm nach.

Basis ^ (Z'' * 2 ^ S) MOD Z == 1

Gut, aber Z'' ist doch gleich Z' / 2^S, dann ist der Exponent der variablen Basis doch Z', oder sehe ich das falsch, wofür dann das ganze Zeug da drunter?
Oder hat N noch eine weitere Bedeutung als die Häufigkeit zu limitieren?

Ansonsten schonmal danke..

zemy hat folgendes geschrieben:

Kannst dann auch einen richtigen nachschieben um sicherzugehen (Teiler suchen von 2 bis Wurzel Zahl).

LOL Eine 30-stellige Zahl besitzt eine (log (10^30))/2 15-stellige Wurzel Int64 ^^

Ne, das mit den SPS-Tests hat schon seine Berechtigung, denn es gibt für n < 10^25 nur knapp eine Handvoll SPSPs und von denen besitzt keine für mehr als 5-10 Basen Starke Pseudo-Primalität. --> Jede Zahl die 10-20 Basen übersteht ist auch wirklich prim.

jelleton hat folgendes geschrieben:

Da frage ich doch noch einmal dumm nach. Basis ^ (Z'' * 2 ^ S) MOD Z == 1 Gut, aber Z'' ist doch gleich Z' / 2^S, dann ist der Exponent der variablen Basis doch Z', oder sehe ich das falsch, wofür dann das ganze Zeug da drunter? Oder hat N noch eine weitere Bedeutung als die Häufigkeit zu limitieren? Ansonsten schonmal danke..

Oops , Schreibfehler meinerseits: S ersetzen durch N.

Ergänzung, wenn ich schonmal dabei bin:
Es reicht theoretisch aus für N = 0 zu testen. Ist dieser Test erfüllt, sind auch alle weiteren erfüllt, da

(B ^ (Z'') mod Z)^2 == 1^2 == 1 ist.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

BenBE hat folgendes geschrieben:

Oops , Schreibfehler meinerseits: S ersetzen durch N. Ergänzung, wenn ich schonmal dabei bin: Es reicht theoretisch aus für N = 0 zu testen. Ist dieser Test erfüllt, sind auch alle weiteren erfüllt, da (B ^ (Z'') mod Z)^2 == 1^2 == 1 ist.

So macht das auch gleich viel mehr Sinn, werds gleich morgen mal ausprobieren, wenns nicht klappt meld ich mich nochmal, ihr wirkt ja recht hilfsbereit/interessiert..

Bis dahin...

Also ich hätte hier ein (wenn auch sehr einfaches) recht schnelles Programm:


Das wichtige ist, dass bei dem Programm nicht geprüft, ob die zu testende Zahl durch jede kleinere Zahl, sondern nur durch jede Primzahl, die kleiner ist, als die zu testende Zahl.

Der Source ist zwar recht einfach, kommt aber sicherlich an die zwischenzeitlich im Thread genannten Ergebnisse nicht ran. Schätz ich mal. Kannst Du mal paar Messwerte nennen, die Du mit dem Source hattest (+HW-Config)

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.