Ausgangslage
Anstatt eine Zahl mit
Millionen von Stellen zu nehmen, begnüge ich mich für das Beispiel mit der 8
Stelligen willkürlichen Zahl 73462537. Diese Zahl teile ich nun durch eine
ebenfallse kleine Mersenne’sche Zahl von (2hoch7)-1=127
Wir können das mal mit
dem Tascherechner ausrechnen:
73462537/127=578445 Rest
22
Wie gesagt, brache ich
für den Lucas-Lehmer Test nur den Rest der Division also 22
Restwerberechnung nach Pitri:
Schritt 1:
Zerlegen der Dezimalen Zahl 73462537 in ihr binaeres Muster, das ergibt:
Binaeres Muster:
100011000001111001100001001
Um eine Dezimalzahl als
Binaerzahl darzustellen habe ich ein Tool gemacht. Hier der Download
Schritt 2:
Nun machen wir Gruppen von diesem Resultat der Länge von unserer Zweierpotenz
der verwendeten Mersenne’schen Zahl. Also Gruppen der Laenge 7
Begonnen wird mit der
niederwertigsten Stelle:
Binaeres Muster:
100011000001111001100001001
Gruppen: 100011 0000011
1100110 0001001
Schritt 3:
Die einzelnen Gruppen welches jeweils binaere Zahlen sind rechnen wir um in
Dezimalzahlen:
Gruppen: 100011 0000011
1100110 0001001
Dezimalzahlen: 35 3 102 9
Schritt 4:
Nun addieren wid die Dezimalen Werte: 35+3+102+9=149
Wenn das Resultat unter
Schritt 4 grösser ist als unsere Mersenne’sche Zahl dann beginnen wir wieder bei
Schritt 1, ansonsten ist das Resultat unter Schritt 4 bereits unser gesuchter
Rest.
Das Resultat under
Schritt 4 ist 149 und grösser als unsere Mersenne’sche Zahl 127, also wieder zu
Schritt 1 mit der Zahl 149 das gibt folgende Ergebnisse:
Schritt 1:
Binaeres Muster von
149=10010101
Schritt 2:
Gruppen: 1 0010101
Schritt 3:
Dezimalzahlen: 1 21
Schritt 4:
Addition 1+21=22
Das Resultat 22 ist
kleiner als 127 also ist es unser Ergebnis.
22 ist der
gesuchte Rest.
Das sieht jetzt ein
bisschen umständlich aus aber es ist super effizient.
Noch eine wichtige
Ergänzung:
Beim Lucas-Lehmer Test
wird jeweils der Rest, der Division mit der Mersenne’schen Zahl als Divisor,
Quadriert. Das heisst also die grösste Zahl welche nach dem Quadrieren
entstehen kann hat maximal doppelt so viele Stellen wie die Mersenne’sche Zahl.
Das heisst also, es gibt maximal zwei Gruppen (Siehe Schritt 2). Das heisst
also, der ganze Algorithmus (schritt 1 bis 4) muss maximal zweimal durchlaufen
werden bis das Resultat feststeht. (Weil zwei Gruppen zusammengezählt niemals
grösser sein können als zweimal die Mersenne’sche Zahl)