GPU-Computing

Magisches Sieb

 aufwärts

Mit dem "magischen Sieb" (magic sieve) [DK 11] lassen sich alle diejenigen Zahlen erzeugen, die teilerfremd zu den Elementen des magischen Siebs S = {2, 3, 5, 7, 11, 17, 23, 29, 47, 53, 59, 83} sind.

Die Zahlen werden erzeugt, indem alle Elemente von ganze Zahlenm*, der multi­plikativen Gruppe modulo m, aufgezählt werden, wobei m der magische Modul ist:

m  =  2 · 3 · 5 · 7 · 11 · 17 · 23 · 29 · 47 · 53 · 59 · 83  =  319514496269430  ungefähr gleich  3·1014

Die Elemente von ganze Zahlenm* werden aufgezählt, indem die Elemente einer zyklischen Untergruppe U erzeugt werden und jeweils mit den Repräsentanten der Nebenklassen von U multi­pliziert werden.

Nachdem ganze Zahlenm* aufgezählt ist, wird mit den Zahlen m + ganze Zahlenm* fortgefahren, dann mit 2m + ganze Zahlenm* usw.

Diese Vorgehens­weise wird im Folgenden anhand eines Beispiels mit kleineren Zahlen verdeutlicht.

Beispiel mit kleinen Zahlen

Als kleines Beispiel arbeiten wir mit dem Sieb S = {2, 3, 5}. Der Modul m ist hier

m  =  2·3·5  =  30

Die Elemente der multi­plikativen Gruppe G = ganze Zahlen30* sind

G  =  { 1, 7, 11, 13, 17, 19, 23, 29 }.

Die Elemente von G sind genau diejenigen Zahlen zwischen 1 und 30, die teilerfremd zu den Elementen 2, 3, 5 des Siebs sind.

Untergruppe

Die Gruppe G enthält eine zyklische Untergruppe U der Ordnung u = 4, die von dem Element g = 7 erzeugt wird:

U  =  spitze Klammer auf7spitze Klammer zu  =  { 7, 19, 13, 1 }

Die gesamte Gruppe besteht aus dieser Untergruppe U sowie einer Nebenklasse von U; diese ergibt sich durch Multi­plikation der Elemente von U mit einem Element, das nicht in U liegt, z.B. mit m-1. Dieses Element ist dann ein Repräsentant der Nebenklasse.

29·U  =  { 23, 11, 17, 29 }

Die gesamte Gruppe ergibt sich somit als

U  vereinigt  29·U

Wir bezeichnen die gewählten Repräsentanten mit ai, i Element {0, ..., h-1}, wobei h = [G:U] der Index von U in G ist. In diesem Beispiel hat U den Index 2 in G. Die Repräsentanten sind a0 = 1 und a1 = 29.

Sieb

Um die Gruppe als Sieb zu verwenden, berechnen wir fortlaufend folgende Zahlen xkij:

xkij  =  k·m + ai·gj mod m

mit   k Element {0, 1, ... },   i Element {0, ..., h-1},   j Element {1, ..., u} sowie mit Modul m und erzeugendem Element g.

In der Reihenfolge ihrer Erzeugung sind dies die Zahlen

7, 19, 13, 1,   23, 11, 17, 29,   37, 49, 43, 31,   53, 41, 47, 59, ...

Diese Zahlen sind genau diejenigen Zahlen, die teilerfremd zu 2, 3, und 5 sind.

Die folgende Python-Generator­funktion erzeugt die Zahlen in der oben angegebenen Reihenfolge bis zu einem limit.

m=30       # Modul
g=7        # erzeugendes Element von U
u=4        # Ordnung der Untergruppe U
h=2        # [G:U], der Index von U in G
a=[1, 29]  # Repraesentanten der Nebenklassen

# Generatorfunktion
def sievedElements(limit):
    x=0
    while x<limit:
        for i in range(h):
            f=a[i]
            for j in range(u):
                f=f*g % m
                yield x+f
        x+=m

Nebenklassen-Repräsentanten des magischen Siebs

Eine gewisse Schwierig­keit besteht darin, geeignete Nebenklassen-Repräsentanten zu finden, wenn der Index [G:U] der Untergruppe U größer als 2 ist. Beim magischen Sieb hat dieser Index den Wert 8192.

Der Ansatz besteht darin, die Isomorphie zwischen G = ganze Zahlenm* und G' = ganze Zahlenp0* × ... × ganze Zahlenpk-1* auszunutzen, wobei p0, ..., pk-1 die Elemente des magischen Siebs sind. Jede dieser Gruppen ganze Zahlenpi* ist zyklisch von der Ordnung pi-1. Wenn alle Zyklen mit jeweiligen erzeugenden Elementen gi parallel gestartet werden, so ist nach kgv(pi-1) Schritten die Ausgangs­situation wieder erreicht, d.h. das Tupel g' = (g0, ..., gk-1) ist erzeugendes Element einer zyklischen Untergruppe U' von G'.

Der Iso­morphismus f zwischen G = ganze Zahlenm* und G' = ganze Zahlenp0* × ... × ganze Zahlenpk-1* ergibt sich als

f(x)  =  (x mod p0 , ..., x mod pk-1).

Mithilfe des chinesischen Restsatzes lässt sich die inverse Abbildung f -1 berechnen.

Die folgende Tabelle gibt erzeugende Elemente gi der Gruppen ganze Zahlenpi* an.
 pi 23571117232947535983
 gi 122323525222

 

Das Element g' = (1, 2, 2, 3, 2, 3, 5, 2, 5, 2, 2, 2) ist erzeugendes Element der zyklischen Untergruppe U' von G'. Umgerechnet in ein Element g Element G ergibt sich

g  =  f -1(g')  =  61393508667977

 

Die Repräsentanten der Nebenklassen werden zunächst auch in G' gebildet und anschließend mithilfe des chinesischen Restsatzes in Elemente von G umgerechnet. In G' ergeben sich die 8192 Repräsentanten als Tupel des folgenden kartesischen Produkts:

{1} × {1,2} × {1,4} × {1,6} × {1,10} × {1,3,6,8} × {1,22} × {1,2,4,12} × {1,46} × {1,2} × {1,58} × {1,82}

Für jede Zahl p des magischen Siebs wird eine dieser Mengen gebildet. Die meisten dieser Mengen sind von der Form {1, p-1}. Wenn jedoch p-1 die Zahl 4 als echten Teiler enthält, bestehen diese Mengen aus anderen Elementen; diese sind durch Ausprobieren ermittelt worden.

Werden diese Tupel mithilfe des chinesischen Restsatzes in Elemente von G umgerechnet, so ergeben sich die Repräsentanten ai der 8192 Nebenklassen von U (einschließ­lich U selbst). Diese sind in der Datei cosetfactors.txt aufgelistet (Achtung: Die erste Zahl 8192 gibt die Anzahl der darauf folgenden Zahlen an).

Zusammenfassung

Zusammen­fassend noch einmal einige Zahlen des magischen Siebs:

Magischer Modulm 319514496269430
Ordnung von G φ(m53820156149760
Generator von Ug 61393508667977
Ordnung von Uu 6569843280
Anzahl der Nebenklassenh 8192
Repräsentanten der Nebenklassen ai  siehe cosetfactors.txt

 

Mit diesen Zahlen lassen sich mithilfe der oben angegebenen Generator­funktion fortlaufend Zahlen bilden, die als Kandidaten für Primzahlen in Frage kommen, weil sie jedenfalls nicht durch eine der Zahlen des magischen Siebs teilbar sind.

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)

 

Weiter mit:   up

 

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