AKS-Primzahltest

[Filip-M. Brinkmann]

Kennt jemand eine bestehende Implementierung dieses Tests?

http://de.wikipedia.org/wiki/AKS-Primzahltest#Der_Algorithmus

Gruesse
Filip

[Gerd K.]

Hi!

Post by Filip-M. Brinkmann
Kennt jemand eine bestehende Implementierung dieses Tests?
http://de.wikipedia.org/wiki/AKS-Primzahltest#Der_Algorithmus

Der AKS-Algorithmus ist nur von theoretischem Interesse. In der Praxis
werden prohabilistische Tests eingesetzt, weil sie sehr viel
schneller sind, z.B. der Miller-Rabin Test. Das ohnehin geringe Risiko
eines Fehlers kann vermindert werden, wenn man zwei unterschiedliche
Tests
nacheinander macht. Dabei ist man immer noch sehr viel schneller,
als es die Umsetzung des AKS je sein kann:

Bestmögliche Laufzeitkomplexität AKS: O((log n)^6)
Laufzeitkomplexität Miller-Rabin: O(c*log n)

So wichtig die Klasse P in der theoretischen Informatik auch ist (
und mit dem AKS wurde ja bewiesen, dass der Test auf Primzahleigenschaft
in P liegt), gibt sie für die Praxis nicht die Garantie der
Einsetzbarkeit: Es gibt sehr "große Polynome" ;-) und polynomiale
Laufzeit sagt nichts über die Praxistauglichkeit eines Algorithmus
aus.

Viele Grüße!
Gerd

[Peter Luschny]

Post by Filip-M. Brinkmann
Kennt jemand eine bestehende Implementierung dieses Tests?
http://de.wikipedia.org/wiki/AKS-Primzahltest#Der_Algorithmus

Auf dieser Seite werden 15 Implementierung angegeben,
allerdings (und wohl mit gutem Grund) keine in Java.

http://fatphil.org/maths/AKS/

[Ingo R. Homann]

Hi,

Post by Peter Luschny

Post by Filip-M. Brinkmann
Kennt jemand eine bestehende Implementierung dieses Tests?
http://de.wikipedia.org/wiki/AKS-Primzahltest#Der_Algorithmus

Auf dieser Seite werden 15 Implementierung angegeben,
allerdings (und wohl mit gutem Grund) keine in Java.

^^^^^
Soll heissen?

Ciao,
Ingo

[Peter Luschny]

Post by Ingo R. Homann

Post by Peter Luschny

Post by Filip-M. Brinkmann
Kennt jemand eine bestehende Implementierung dieses Tests?
http://de.wikipedia.org/wiki/AKS-Primzahltest#Der_Algorithmus

Auf dieser Seite werden 15 Implementierung angegeben,
allerdings (und wohl mit gutem Grund) keine in Java.

^^^^^
Soll heissen?

Effizienz beim Programmieren, Effizienz beim Ausführen,
Übersichtlichkeit des Codes - sind in bei anderen Sprachen,
und ich zähle da Maple und Mathematica dazu, oftmals
deutlich höher. Ich bin auch noch nie auf die Idee gekommen,
ein Content-Management-System mit Maple zu schreiben.

Alles Dinge, die hier doch bei ähnlichen Themen schon
ausführlich diskutiert worden sind - kürzlich erst im
Zusammenhang mit Fortress.

Ich hatte damals AKS in Maple implementiert. Hier noch
ein Beispiel, das ich erst dieser Tage geschrieben habe.

http://www.luschny.de/math/factorial/approx/continuedfraction.html

15 Zeilen Maple, 45 Zeilen C# (nicht nachgezählt).

Und dann sage ich da auch noch:

"If implemented in Java the program turns almost
unreadable because Java does not support operator
overloading."

Gruss Peter

[Ingo R. Homann]

Hi,

Post by Peter Luschny

Post by Ingo R. Homann

Post by Peter Luschny
Auf dieser Seite werden 15 Implementierung angegeben,
allerdings (und wohl mit gutem Grund) keine in Java.

^^^^^
Soll heissen?

Effizienz beim Programmieren,
Übersichtlichkeit des Codes

Das ist sicher eine individuelle (Geschmacks-)Frage.

Post by Peter Luschny
Effizienz beim Ausführen,

Da kommt es darauf an, wie "geschickt" man in der jeweiligen Sprache
programmieren kann.

Post by Peter Luschny
Ich bin auch noch nie auf die Idee gekommen,
ein Content-Management-System mit Maple zu schreiben.

Nun, der Unterschied ist: Maple und Mathematica sind sehr spezialisierte
Sprachen, Java ist versteht sich als "genaral-purpose"-Sprache. Dass man
in einer extrem spezialisierten Sprache nicht auf die Idee kommt, in ein
völlig fremdes Spazialgebeit eindringen zu wollen, ist nachvollziehbar.

Andersrum ist es aber häufig doch so, dass man mit einer
general-purpose-Sprache (in der man eine bestimmte Anwendung entwickelt)
in Gebiete hineinkommt, die zwar doch recht speziell sind, es aber
trotzdem in den meisten Fällen nicht rechtfertigen, einen entsprechnden
"Adapter" zu der Spezial-Sprache zu programmieren (sofern das überhaupt
möglich ist), vom Benutzer zu verlangen, zusätzlich diese Sprache zu
installieren, und dann auch noch - möglicht Betriebssystemunabhängig -
alles auf verschiedener Hardware- und Software-Konfiguration lauffähig
zu halten.

Und - ohne den AKS-Algorithmus zu kennen - vermute ich, dass er nun
nicht so extrem komplex ist, dass er sich nur mit verrenkungen in Java
lösen ließe.

Meine Vermutung ist eher, dass es (unter Mathematikern?) immer noch
starke Vorbehalte gegen Java gibt.

Ciao,
Ingo

[Paul Ebermann]

Post by Peter Luschny

Post by Filip-M. Brinkmann
Kennt jemand eine bestehende Implementierung dieses Tests?
http://de.wikipedia.org/wiki/AKS-Primzahltest#Der_Algorithmus

Auf dieser Seite werden 15 Implementierung angegeben,
allerdings (und wohl mit gutem Grund) keine in Java.

Hmm, wäre der Unterschied eigentlich mehr als im O()?
Falls nicht, wie groß würdest du den Faktor (z.B.
im Vergleich mit deiner Maple-Implementation) schätzen?

Post by Peter Luschny
http://fatphil.org/maths/AKS/

Und, ist die thank-you-Mail inzwischen angekommen?

:-)


Paul