Diskussion:Solovay-Strassen-Test

Korrektheit

Die Formulierung dass der Test unkorrekte Aussagen treffen kann ist ungünstig. Der Test erkennt entweder (mit einer gewissen Wahrscheinlichkeit) eine Nichtprimzahl oder er trifft keine Aussage. Ich habe angefangen diese Unterscheidung in den Artikel einzupflegen, das sollte so fortgeführt werden.

Anmerkung zur Laufzeit: Da alle Berechnungen in der Schleife in O(log n) möglich sind, beträgt die Laufzeit O(k*log n) bei k Schleifeniterationen.