1. Aufgabe und probablePrime

[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]

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]

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]

wie wärs mit dem? http://de.wikipedia.org/wiki/AKS-Primzahltest

[Dennis Albrecht]

wie wärs mit dem? http://de.wikipedia.org/wiki/AKS-Primzahltest

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.

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_]

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.

[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]

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

wie wärs mit dem? http://de.wikipedia.org/wiki/AKS-Primzahltest

...

muss ich nix weiter zu sagen, merkste selbst oder?

[Dennis Albrecht]

...
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. Vielleicht entsteht daraus ja mal der ultimative Primzahltest.

Gruß

[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.