1. Aufgabe und probablePrime

Uhr
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 30. Sep 2010 17:14

1. Aufgabe und probablePrime

Beitrag von Uhr »

Hi

BigInteger.probablePrime generiert in Java Primzahlen mit einer sehr hohen Wahrscheinlichkeit. Auf der Suche nach sicheren Alternativen bin ich immer wieder über den Kommentar gestolpert, dass man in der Praxis durchaus diese "unsicheren" Methoden einsetzt, da alles andere viel zu langsam sei. Deshalb würde ich gerne wissen, ob der Einsatz von probablePrime in der ersten Aufgabe der Hausübung ohne weiteren Check in Ordnung ist, oder ob wir die Korrektheit der Primzahlen mit 100%iger Wahrscheinlichkeit garantieren sollen.

Jerome Reinländer
Neuling
Neuling
Beiträge: 6
Registriert: 17. Apr 2010 11:50

Re: 1. Aufgabe und probablePrime

Beitrag von Jerome Reinländer »

Also wenn ich mich recht entsinne meinte unser Tutor, das sei ok. Mal abgesehen davon kriegst du fuer eine Genauigkeit von 100 mit einer Wahrscheinlichkeit von (1-0.5^100)% eine Primzahl, was recht genau ist...

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: 1. Aufgabe und probablePrime

Beitrag von Steven »

Ein probabilistischer Primzahlentester genügt vollkommen, wenn die Irrtumswahrscheinlichkeit hinreichend klein gewählt wird. In der Praxis nimmt auch niemand exakte Verfahren, weil die deutlich zu langsam wären.

Mir fällt spontan auch kein exaktes Verfahren ein, das signifikant schneller wäre als eine Faktorisierung.

einalex
Nichts ist wie es scheint
Beiträge: 23
Registriert: 23. Aug 2010 13:40

Re: 1. Aufgabe und probablePrime

Beitrag von einalex »


Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: 1. Aufgabe und probablePrime

Beitrag von Dennis Albrecht »

einalex hat geschrieben:wie wärs mit dem? http://de.wikipedia.org/wiki/AKS-Primzahltest
http://images.apple.com/acg/pdf/aks3.pdf hat geschrieben:A 30-decimal-digit prime thus took, on a 1 GHz.
Apple G4 machine, “about a day” to be resolved.
30 dezimale Stellen sind 100 bit. Unsere Primzahlen sind im Bereich 265 bit. Ich räume ein, dass der Wert von 2003 ist, aber für beide Primzahlen brauchst du (unter der Annahme, dass du direkt echte Primzahlen rätst) mindestens ein viertel Jahr. Kannst also jetzt anfangen und nächstes Jahr dann wieder EiTS belegen. Und hoffentlich gab es zwichenzeitlich keinen Stromausfall.
http://de.wikipedia.org/wiki/Primzahl hat geschrieben:Mit dem AKS-Primzahltest ist es möglich, Zahlen in polynomialer Laufzeit zu testen. Allerdings ist er in der Praxis deutlich langsamer als der Miller-Rabin-Test.
Die probablePrime-Methode (, die, wenn mich nicht alles täuscht, auch den Miller-Rabin-Test nutzt, ) braucht nur Bruchteile einer Sekunde. Ich will nicht bezeifeln, dass der AKS-Primzahltest eine Deseinsberechtigung hat, aber er ist halt, bis heute, nicht wirklich geeignet, da sich der Aufwand nur für bestimmte Bereiche (was weiß ich, Geheimdienst etc.) lohnt.

Gruß Dennis

Mirlix_
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 188
Registriert: 3. Mär 2006 14:57

Re: 1. Aufgabe und probablePrime

Beitrag von Mirlix_ »

Noch eine andere Frage, dürfen wir wenn wir BigInteger in Java nehmen die modInverse Funktionen nutzen, für mich ist das modulare Arithmetik und somit erlaubt. Es könnte aber auch verlangt sein das wir das mit dem erweiterten Euklid berechnen sollen. Zaehlt die Funktion noch zu modularer Arithmetik und ist somit erlaubt oder nicht? Danke für die Antwort.
"If you want more effective programmers, you will discover that they should not waste their time debugging, they should not introduce the bugs to start with." Edsger W. Dijkstra

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: 1. Aufgabe und probablePrime

Beitrag von Dennis Albrecht »

Da von Tutoren- und Veranstalterseite noch nichts kam, würde ich dir mal raten, von dieser Methode Abstand zu nehmen, da der Euklid sonst nicht viel leisten würde.

Gruß

einalex
Nichts ist wie es scheint
Beiträge: 23
Registriert: 23. Aug 2010 13:40

Re: 1. Aufgabe und probablePrime

Beitrag von einalex »

Steven hat geschrieben:Mir fällt spontan auch kein exaktes Verfahren ein, das signifikant schneller wäre als eine Faktorisierung.
einalex hat geschrieben:wie wärs mit dem? http://de.wikipedia.org/wiki/AKS-Primzahltest
Dennis Albrecht hat geschrieben:...
muss ich nix weiter zu sagen, merkste selbst oder?

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: 1. Aufgabe und probablePrime

Beitrag von Dennis Albrecht »

einalex hat geschrieben: ...
muss ich nix weiter zu sagen, merkste selbst oder?
Ich weiß worauf du hinaus willst, aber um Prof Koch zu zitieren (Gedächtnisprotokoll):
Was hilfts eine Methode mit konstanter Laufzeit zu haben, wenn das k sehr groß ist.
Ähnlich verhält es sich mit dem AKS.
Daher will ich noch abschließend sagen (ich will das hier jetzt nicht noch tagelang breittreten):
Schönes, schnelles Verfahren (ich hatte vorher auch noch nichts von gehört gehabt, daher danke, dass du es mir nahe gebracht hast), aber schneller bedeutet halt nicht (immer) auch schnell genug.
Aber es wollen ja auch künftige angehende Professoren und Doktoren noch etwas zu schreiben haben. :D Vielleicht entsteht daraus ja mal der ultimative Primzahltest.

Gruß

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: 1. Aufgabe und probablePrime

Beitrag von Blub »

AKS ist zu langsam, und wie steven schon sagte reicht der probabilistische Primzahlgenerator. Pseudoprimzahlen reichen hier vollkommen aus.

Und nein, modinverse ist nicht erlaubt.
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

Antworten

Zurück zu „Archiv“