kleiner Fermats Satz, große

[Daniel Thoma]

Hallo Andavos,

Oder durch Zerlegung, daran werde ich mich jetzt machen.

Was willst Du denn wie zerlegen?

P.S. Das soll nicht Kryptologisch sicher sein, aber unser Lehrer meinte es gäbe keine Formel um Primzahlen zu testen, nur das Sieb verfahren.
Naja da wollte ich ein Programm schreiben das Primzahlen bis ~100 000 testen kann, _ohne_ das Sieb des Eratosthenes zu benutzen.

Naja, damit hast Du die Aussage Deines Lehrers nicht wiederlegt. Da dieser Test eben auch nicht-Primzahlen erkennt.
Tatsächlich kann man Primzahlen aber viel schneller als mit dem Sieb erkennen.
Es geht sogar in Polynomialzeit: < http://de.wikipedia.org/wiki/AKS-Methode>

Grüße

Daniel