... Reinecke¹

e-mail: reinecke@thorstenreinecke.de

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Fibonacci-Folge²

Sie sollten sich den Stammbaum aufzeichnen und die Rekursionsformel über eine nach Geschlechtern getrennte Betrachtung herleiten.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...³

Der erste Mensch, der diese Eigenschaft »entdeckt« hat, wird natürlich L_n : = F_n+1 + F_n-1 gesetzt und anschließend die zugehörigen Startwerte ermittelt haben.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...⁴

Es sei ausdrücklich erwähnt, daß die Induktion auf k basiert und damit auch für negative Werte von n gültig ist!

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... gilt⁵

Das ist übrigens eine sehr interessante Eigenschaft, wenn man F_N für zusammengesetzte N faktorisieren möchte!

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... erhalten⁶

Wir lassen hierfür auch reelle Zahlen als Folgenwerte zu und treffen zusätzlich folgende Feststellungen:

Für alle Fibonaccifolgen f und g sowie jedem reellen Skalar $\alpha$ gilt:

(f $$\oplus$$ g)_n : = f_n + g_n = f_n-1 + f_n-2 + g_n-1 + g_n-2 = (f $$\oplus$$ g)_n-1 + (f $$\oplus$$ g)_n-2

($$\alpha$$$$\bullet$$f )_n : = $$\alpha$$ ^. f_n = $$\alpha$$ ^. (f_n-1 + f_n-2) = $$\alpha$$ ^. f_n-1 + $$\alpha$$ ^. f_n-2 = ($$\alpha$$$$\bullet$$f )_n-1 + ($$\alpha$$$$\bullet$$f )_n-2

Jede Linearkombination zweier gegebener Fibonaccifolgen ist somit ebenfalls eine Fibonaccifolge. Die beiden Funktionsterme (${\frac{{1+\sqrt{5}}}{{2}}}$)ⁿ sowie (${\frac{{1-\sqrt{5}}}{{2}}}$)ⁿ sind geschlossene Ausdrücke für zwei verschiedene Fibonaccifolgen. Die nachfolgend aufgestellte Linearkombination ist also die geschlossene Form einer Fibonaccifolge.

Etwas abstrakter betrachtet bilden die Fibonaccifolgen somit einen zweidimensionalen Unterraum des (unendlichdimensionalen) Vektorraums aller Folgen. Die beiden ausgewählten Funktionsterme bilden zusammen ein Erzeugendensystem dieses zweidimensionalen Vektorraums.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...⁷

Und tatsächlich wird ein derartiges Verfahren auch vom Matheprogramm MAPLE verwendet, um Fibonaccifolgenwerte zu bestimmen.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... aufgerufen⁸

Wenn in Restklassen gerechnet wird, dürfen sich diese nicht ändern.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Satzes⁹

(a + b)ⁿ = $\sum_{{i=0}}^{{n}}$$\binom {n}{i}$a^{i .} b^n-i mit Binomialkoeffizient $\binom{n}{k}$ : = ${\frac{{n!}}{{k!\cdot(n-k)!}}}$, bekannt aus dem Pascalschen Dreieck

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹⁰

Der explizite Ansatz, Fibonaccifolgen zu verwenden, ist eine Eigenkonstruktion und in gewisser Weise eine Spezialisierung des in der Literatur bereits hinlänglich bekannten (p+1)-Algorithmus.

Hier geht es weniger um ausgefeilte Effizienz als um die Grundidee! Der interessierte Leser möge für Optimierungsansätze z.B. [PLMo87] zu Rate ziehen.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... zerfällt¹¹

oder (ganz allgemein) F_K $\equiv$ 0 ( mod p) erfüllt ist (denn wegen F_2n = F_nL_n können sich auch Teiler der L_n dazugesellen, die nicht die obige Struktur aufweisen)

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Primzahlen¹²

Da kleine Primzahlen die gesuchte Zahl K möglicherweise mehrfach teilen, mag es nicht nur erlaubt, sondern sogar erwünscht sein, wenn sie auch in h mehrfach auftreten.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹³

Denn der Primfaktor kann auch Teiler einer in F_K enthaltenen Lucaszahl sein! Beispiel: p : = 1974737795746080149567; es ist p + 1 = 2^{6 .} 3^{3 .} 7 ^. 47 ^. 515894844583 ^. 6733, aber es gilt trotzdem gcd(F_{2^{6 .} 3^{2 .} 7}, p) = p, weil gcd(L_{2^{5 .} 3^{2 .} 7}, p) = p ist...

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹⁴

Die Ermittlung der Multiplikationsformel und die Untersuchung der Struktureigenschaften des charakteristischen Polynoms sollten Sie dann allerdings einem Computeralgebrasystem überlassen.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹⁵

Dies dürfte auch der Grund dafür gewesen sein, warum Lenstra den genialen Einfall hatte, elliptische Kurven zu verwenden: Er hat die Template-Eigenschaft des (p-1)-Algorithmus erkannt und ihre Verwendbarkeit für elliptische Kurven gesehen!

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.