Suche nach Wieferich-Primzahlen

 aufwärts

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

Definition

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

2p-1  kongruent  1  (mod p)

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

2p-1  kongruent  1  (mod p2)

Diese Primzahlen heißen Wieferichzur Person-Primzahlen. Interessanter­weise sind bisher nur zwei Wieferich-Primzahlen bekannt: 1093 und 3511.

Es ist nicht bekannt, ob es weitere Wieferich-Primzahlen gibt. Bisher wurde offenbar nur bis zur Größen­ordnung 1015 nach weiteren Wieferich-Primzahlen gesucht, mit negativem Ergebnis [DK 11].

Wieferich-Primzahlen haben nicht nur theoretische, sondern auch praktische Bedeutung. Ein Anwendungs­fall ist der Primzahl­potenz-Test, dort müssen Wieferich-Primzahlen gesondert berück­sichtigt werden.

Wieferich-Test

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

2p-1 mod p2 = 1

Wenn ja, so ist p eine Wieferich-Primzahl.

Suche

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. Eine schnelle Erzeugung von Primzahl­kandidaten ist möglich mit dem magischen Sieb, wie in [DK 11] beschrieben.

Arithmetik

Da beim Wieferich-Test modulo p2 gerechnet wird, sind Zahlen in der Größen­ordnung 1032 entsprechend 106 Bit erforderlich. Hierfür ist eine ent­sprechende Integer-Arithmetik erforderlich.

Zu prüfen ist gegebenen­falls auch, ob die Berechnungen sich mithilfe der Montgomery-Multi­plikation beschleunigen lassen.

Andere Basen

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.

Literatur

[DK 11]F.G. Dorais, D. Klyve: A Wieferich Prime Search up to 6.7 10^15. Journal of Integer Sequences, Vol. 14 (2011)
https://cs.uwaterloo.ca/journals/JIS/VOL14/Klyve/klyve3.pdf

 

 

 Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 07.10.2013   Updated: 07.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik