Primzahltests interaktiv

Sieb des Eratosthenes: (Source)
Ihr Browser kann leider kein Java!!

Satz(Wilson's Test) n ist prim gdw. . (Source) Ihr Browser kann leider kein Java!!

Lucas's Test

Probabilistische (Monte Carlo) Primzahltests

Fermat-Test

SatzPR co-RP

DefinitionFür p prim sei

Legendre Symbol

Sei Primpotenzzerlegung einer ungeraden Zahl n, so ist das Jacobi Symbol

Satz(Euler's Kriterium:) , prim , .

Satz prim .

Solovay-Strassen-Test: Wähle zufälliges a<p und prüfe .

Patt's nichtdeterministischer Primzahltest

DefinitionFermat-Paar, Ordnungsrelation, rank, Pratt-Sequenz,

SatzFür ein Fermat-Paar (a,n) gilt gdw. n prim und a erzeugt

SatzFür alle n>1 gilt n prim gdw. ein Fermatpaar existiert.

SatzPR NP co-NP