Wieferich-Primzahlen

Eine Anwendung, die sich möglicherweise für GPU-Computing eignet, ist die Suche nach Wieferich-Primzahlen.

Nach dem Satz von Fermat gilt für jede Primzahl n > 2

2^n-1 kongruent 1 (mod n)

Es gibt aber auch Primzahlen, für die gilt:

2^n-1 kongruent 1 (mod n²)

Diese Primzahlen heißen Wieferich-Primzahlen. Interessanterweise sind bisher nur zwei Wieferich-Primzahlen bekannt: 1093 und 3511 [Web 1].

Es ist nicht bekannt, ob es weitere Wieferich-Primzahlen gibt. Bisher wurde offenbar nur bis zur Größenordnung 10¹⁵ nach weiteren Wieferich-Primzahlen gesucht, mit negativem Ergebnis [Web 2].

Wieferich-Primzahlen haben nicht nur theoretische, sondern auch praktische Bedeutung. Ein Anwendungsfall ist der Primzahlpotenz-Test, dort müssen Wieferich-Primzahlen gesondert berücksichtigt werden.

Es wird geprüft, ob für die Primzahl p gilt

2^p-1 mod p² = 1

Wenn ja, so ist p eine Wieferich-Primzahl.

Ein mögliches Verfahren, um weitere Wieferich-Primzahlen zu suchen, besteht darin, eine Primzahl nach der anderen daraufhin zu testen, ob sie Wieferich-Primzahl ist.

Das Problem hierbei ist die Erzeugung der Primzahlen. Es ist zu aufwendig, eine ungerade Zahl nach der anderen zu erzeugen, um den Wieferich-Test darauf anzuwenden.

Für jede kleine Primzahl p aus der Menge {3, 5, 7, 11, 13, ..., P} wird ein modulo-p-Zähler geführt. Für die (ungerade) Startzahl n = 10¹⁵+1 werden die Zähler mit jeweils n mod p initialisiert. Dann wird n um 2 weitergezählt, zugleich werden alle Zähler um 2 weitergezählt. Erreicht ein Zähler seinen Wert p, wird er auf 0 gesetzt. Hat irgendein Zähler den Wert 0, so ist n zusammengesetzt, da durch das entsprechende p teilbar, ansonsten ist n ein Kandidat für den Wieferich-Test.

Da beim Wieferich-Test modulo n² gerechnet wird, sind Zahlen in der Größenordnung 10³² entsprechend 106 Bit erforderlich. Die erforderliche Integer-Arithmetik muss aus der vorhandenen 32-Bit-Integer-Arithmetik aufgebaut werden (oder aus 64-Bit-Gleitkomma-Arithmetik?).

Anstelle der Basis 2 des Wieferich-Tests lassen sich auch andere Zahlen als Basis wählen, etwa 3 oder 5. Als Wieferich-Primzahlen zur Basis 3 sind bisher nur 11 und 1006003 bekannt. Als Wieferich-Primzahlen zur Basis 5 sind bisher bekannt: 20771, 40487, 53471161, 1645333507, 6692367337 und 188748146801.