Der kleine Satz von Fermat

Der Miller-Rabin Test

Der Miller-Rabin Test ist ein probabilistischer Primzahltest, der als optimierte Version des klassischen Primzahltestes betrachtet werden kann. Ähnlich wie der Fermat’sche Test wird überprüft, ob eine Eigenschaft von Primzahlen auch für eine gegebene Zahl gilt. Dafür definiert man zuerst die starken Pseudoprimzahlen.

Starke Pseudoprimzahlen

Sei [math]n\gt 2[/math] eine natürliche, ungerade Zahl. [math]n[/math] lässt sich schreiben als [math]2^s\cdot d+1[/math], wobei [math]s,d[/math] natürliche Zahlen sind und [math]d[/math] ungerade. Sei nun [math]a\lt n[/math] eine natürliche Zahl. Man nennt [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math], wenn [math]n[/math] eine der folgenden Bedingungen erfüllt:

• [math]a^d\equiv1\ mod\ n[/math]
• [math]a^{2^rd}\equiv-1\ mod\ n[/math] für eine beliebige, natürliche Zahl [math]0\le\ r\lt s[/math]