Ich beschäftige mich momentan mit dem Solovay-Strassen-Algorithmus.
Ich verstehe nicht genau weshalb die Fehlerwahrscheinlichkeit bei Jac(a/n)=a^{(n-1)/2} (mod n) so hoch (max. 50%) ist.
Das Eulersche-Kriterium erscheint mir nämlich schon sehr zuverlässig, was den Primzahltest angeht. Und zwar, weil:
1. es im Vergleich zu der Gesamtzahl an ungeraden Zahlen nur wenige Eulersche Pseudoprimzahlen gibt (trotzdem unendlich)
2. diese zusätzlich nur zu bestimmten Basen "pseudoprim" sind.
Wenn man sich also z.B. 341 ansieht (11 * 31) hat diese Pseudoprimzahl "nur" 100 Basen zu der sie Pseudoprim ist (wenn ich mich nicht verzählt habe), also als Ergebnis 1 oder -1 liefert (quadratischer/nicht-quadratischer Rest).
Mit einer zufälligen Basis a, beträge die Fehlerwahrscheinlichkeit der Aussage "341 ist eine Primzahl" also "nur" ~29%, wenn man das Eulersche Kriterium mit 341 anwendet.
Ist das in diesem Fall einfach eine "günstige" Pseudoprimzahl bzw. gibt es Pseudoprimzahlen, bei denen die Fehlerwahrscheinlichkeit >50% ist?
Wenn man nun noch Jac(a/n) und a^{(n-1)/2} (mod n) vergleicht, kann ich mir kaum vorstellen, dass es ein "worst-case" n gibt, bei dem die Häfte der Elemente 0<a<n-1 zu einer Gleichheit führen kann, obwohl n zusammengesetzt ist.
Ich könnte es mir momentan nur dadruch erklären, dass es Eulersche Pseudoprimzahlen n zu mehr als n/2 Basen gibt, also die Fehlerwahrscheinlichkeit des Eulerschen Kriteriums mit einem n bei zufälligen a, 0<a<p-1, bei mehr als 50% liegen kann.
Der Vergleich mit dem Jacobi-Symbol würde dann die Häufigkeit von Zeugen(a), 0<a<n-1, für n /= prim auf Anzahl Zeugen(a) >= n/2 garantieren.
