Primzahl mit probalistischem V < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Testen Sie mit dem probabilistischen Verfahren für verschiedene Zahlen, ob sie prim sind, unter anderem: 15, 341, 2701. Testen Sie mit mehreren Basen, insbesondere bei 15 auch mit 11
|
Hallo Ihr Lieben,
ich schon wieder. Leider habe ich die Aufgabe mal wieder gar nicht verstanden. Das Wort Probalistisches Verfahren hab ich noch nie gehört und bei dem, was ich im Internet gefunden habe nicht kapiert. Ich denke mal, weil in der Aufgabenstellung etwas von verschiedenen basen steht, dass ich die Darstellung von fermat beweisen soll, also nicht einfach 3*5= 15, also keine Primzahl?
341 ist nicht durch 2,3,5, 7, aber durch 11 teilbar, also 341 = 11 * 31, also keine Primzahl
2701 ist nicht durch 2,3,5,7,11,13, 17, 19,23,. geh ich jetzt erstmal mit Sieb des Erathosthenes durch, aber das ist wohl nicht das was er haben will.
Kann mir jemand an einem einfachen Beispiel erklären was der Prof meint??
Tausend Dank Snoopy
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:34 Sa 27.10.2007 | | Autor: | Snoopymaus |
Also nach dem Sieb des Erathostenes sind die Primzahlen unter 100:
2, 3, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 89, 97
nun muss ich zur Prüfung der Zahl 2701 nur bis 53 durchprobieren, da alle kleineren Primzahlen bereits überprüft sind und 53*53 > 2701 ist.
2701 ist also so überprüft keine Primzahl, da 2701 = 37*73
Aber das hat vermutlich mit dem probalistischen Verfahren nichts zu tun??
Gruß Snoopy
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:58 Sa 27.10.2007 | | Autor: | koepper |
Hi Snoopy,
es gibt mehrere probabilistische Primzahltests. Wenn du eine vermeintliche Primzahl so testest und sie fällt durch, dann ist sie ganz sicher zusammengesetzt. Fällt sie aber nicht durch, dann ist noch nicht ganz gesichert, daß die Zahl prim ist.
Der einfachste Test dieser Art für eine Zahl p ist der sog. Fermat-Test:
Dazu wählst du eine Basis b, die teilerfremd zu p ist und prüfst [mm] $b^{p-1}$ [/mm] mod p. Wenn das Ergebnis 1 ist, dann hat die Zahl diesen Test bestanden.
Nun ist es für die meisten zusammengestzten Zahlen so, daß die Wahrscheinlichkeit für das Bestehen des Tests höchstens 50 % beträgt. Wenn du also 20-30 mal mit verschiedenen Basen testest und die Zahl p besteht alle diese Tests, dann ist die Wahrscheinlichkeit, daß sie trotzdem zusammengesetzt ist, verschwindend gering.
Das dumme ist nur, daß es ganz bestimmte Zahlen gibt, die jeden solchen Test bestehen aber trotzdem zusammengesetzt sind. Das sind die sogenannten Carmichael-Zahlen. Wenn du also nicht von vornherein weißt, daß du es nicht mit einer Carmichael-Zahl zu tun hast, dann ist der Fermat-Test unzuverlässig.
Es gibt aber verbesserte Tests. Der gebräuchlichste ist der sog. Rabin-Miller-Test.
Aber schau erstmal, mit welchem du testen sollst.
Gruß
Will
|
|
|
| |
|
hi Will, tausend Dank, aber den Sinn von einem solchen Verfahren verstehe ich nicht wirklich, dann hab ich doch viel schneller das Sieb des Eratosthenes durchprobiert und wenn ich dann bei Wurzel der Zahl angelangt bin, dann weiss ich 100% sicher ob es eine Primzahl ist oder weshalb nicht.
Wo liegt also der Sinn solcher Verfahren?? Hast Du mal ein Beispiel, das Du mir vorrechnen kannst? Oder was glaubst Du will mein Prof jetzt da stehen haben??
Und vielen Dank für Deine Antwort.
Gruß Snoopy
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:46 Sa 27.10.2007 | | Autor: | koepper |
Hallo Snoopy,
ein Beispiel kannst du dir doch leicht selbst machen für die Anwendung des Verfahrens von Fermat.
Anstelle einer Antwort auf die Frage, warum man das nicht besser mit dem Siebverfahren macht, bitte ich dich einfach mal mit dem Siebverfahren zu überprüfen, ob die Zahl
9983243247875748975930224275675567567463522425678868686746463523424244455345465667765776756756775775675675677
prim ist oder nicht.
Wenn du jetzt sagst, so etwas bräuchte man in der Praxis nicht, weit gefehlt. Für Verschlüsselungsverfahren (RSA) verwendet man sogar noch wesentlich größere Zahlen als diese.
LG
Will
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:47 Mo 29.10.2007 | | Autor: | Snoopymaus |
Hm, danke Will, irgendwie widerstrebt es mir ein Verfahren anzuwenden, von dem ich weiss, dass es mir nicht sicher sagt, ob ich nun eine Primzahl habe oder nicht. Diese Rumprobiererei. Also ich glaube ich würde dann eher das Sieb des Eratosthenes für riesige Zahlen programmieren. 
Aber ich denke er wollte Fermat, denn Fermat ist zumindest mal im Script erwähnt, da werd ich halt mal rangehen.
gruß und lieben Dank
Snoopy
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:25 Mo 29.10.2007 | | Autor: | koepper |
Hallo Snoopy,
> Hm, danke Will, irgendwie widerstrebt es mir ein Verfahren
> anzuwenden, von dem ich weiss, dass es mir nicht sicher
> sagt, ob ich nun eine Primzahl habe oder nicht. Diese
> Rumprobiererei.
Das hat nichts mit Rumprobieren zu tun. Indem du eine mögliche Primzahl oft genug dem Test unterziehst, kannst du die Irrtumswahrscheinlichkeit so weit drücken wie du willst.
Schon nach 10 Tests liegt die Irtumswahrscheinlichkeit deutlich unter 0,1%, nach 20 Tests unter 0,0001%.
Und wenn du den Test vielleicht 200 mal über eine Zahl laufen läßt, was für einen Computer heutzutage ein Kinderspiel ist, dann ist die Wahrscheinlichkeit, daß eine zusammengesetzte Zahl unerkannt bleibt geringer als daß die Erde in den nächsten 5 Minuten von einem Meteoriten getroffen wird.
Das gilt beim Rabin-Miller Test generell und beim Fermat-Test natürlich nur abgesehen von den Carmichael-Zahlen.
Du solltest den Fermat-Test trotzdem verstehen, weil er extrem einfach ist und weil er Grundlage des verbesserten Rabin-Miler Tests ist.
> Also ich glaube ich würde dann eher das
> Sieb des Eratosthenes für riesige Zahlen programmieren.
Dann hast du nicht verstanden, was ich schrieb: Das ist nicht praktikabel für große Zahlen.
Für die von mir angegebene Zahl bräuchtest du schon länger als unser Universum existiert, um sie mit dem Sieb zu testen.
>
> Aber ich denke er wollte Fermat, denn Fermat ist zumindest
> mal im Script erwähnt, da werd ich halt mal rangehen.
Probier es erstmal mit kleinen Zahlen zum Verstehen 
Gruß
Will
|
|
|
|
