Satz von Lamé

Der Satz von Lamé ist ein Satz in der Zahlentheorie, der eine obere Grenze für die Anzahl der Schritte liefert, die der euklidische Algorithmus zur Berechnung des größten gemeinsamen Teilers (ggT) zweier Zahlen benötigt. Er wurde 1844 von Gabriel Lamé bewiesen. Der Satz ist von besonderem Interesse in der Komplexitätstheorie und hat Anwendungen in der Kryptographie, insbesondere bei der Analyse von Algorithmen zur Faktorisierung großer Zahlen.

Formulierung des Satzes

Im euklidischen Algorithmus für den größten gemeinsamen Teiler zweier natürlicher Zahlen $u$ und $v$ ist die Zahl der Divisionsschritte höchstens fünfmal so groß wie die Stellenzahl der kleineren der gegebenen Zahlen (im Dezimalsystem).

Bedeutung und Anwendungen

Der Satz von Lamé ist insbesondere für die Effizienz des Euklidischen Algorithmus von Bedeutung, da er die Komplexität des Algorithmus in Bezug auf die Eingabewerte (die Zahlen a und b) beschreibt. Da die Anzahl der Schritte des Algorithmus in der Regel mit dem logarithmischen Wachstum der Eingabewerte skaliert, kann der Euklidische Algorithmus auch bei sehr großen Zahlen effizient ausgeführt werden. Dies ist besonders relevant für Anwendungen in der Zahlentheorie und Kryptographie, wie etwa bei der Berechnung von modularen Inversen oder bei der Faktorisierung großer Zahlen.

In der Kryptographie wird der Euklidische Algorithmus unter anderem für die Analyse der RSA-Verschlüsselung genutzt, die auf der Berechnung des größten gemeinsamen Teilers angewiesen ist. Die effiziente Berechnung dieses Teilers ist entscheidend für die Sicherheit von RSA. Der Satz von Lamé bietet eine theoretische Grundlage für die Schnelligkeit und Effizienz solcher kryptografischen Verfahren.

Historischer Hintergrund

Der euklidische Algorithmus selbst wurde in der Antike von Euklid beschrieben und stellt eine Methode dar, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen. Der Algorithmus basiert auf der Idee der sukzessiven Division mit Rest. Nach Donald E. Knuth handelt es sich um den ältesten nicht-trivialen Algorithmus, der bis heute verwendet wird. Der Satz von Lamé wird aufgrund der Veröffentlichung von 1844 traditionsgemäß dem französischen Mathematiker Gabriel Lamé zugeordnet. Es gab aber frühere Erkenntnisse zu diesem Thema. Antoine-André-Louis Reynaud gab bereits vor 1811 eine grobe Schranke für die Laufzeit des Algorithmus an. Émile Léger kannte Lamés grundlegendes Ergebnis schon 1837. Pierre-Joseph-Étienne Finck fand 1841 einen anderen Beweis des Satzes.

Beweis des Satzes

$u$ und $v$ seien zwei natürliche Zahlen mit $u>v$. Die Anwendung des euklidischen Algorithmus liefert zwei Folgen $(q_{1},\ldots ,q_{n})$ und $(v_{2},\ldots ,v_{n})$ von natürlichen Zahlen, sodass (mit $v_{0}=u$, $v_{1}=v$ und $v_{n+1}=0$)

$v_{i-1}=q_{i}v_{i}+v_{i+1}$

für $i=1,\ldots ,n$ und

$u>v>v_{2}>\cdots >v_{n}>0$ gilt.

$n$ ist die Zahl der Schritte des euklidischen Algorithmus, es gibt die Zahl der durchgeführten Divisionen mit Rest an.

Die Fibonacci-Zahlen sind definiert durch $f_{0}=0,$ $f_{1}=1$ und

$f_{n+1}=f_{n}+f_{n-1}$

für $n>0.$

Die oben angegebenen Beziehungen zeigen, dass $v_{n}\geq 1=f_{2}$ und $v_{n-1}\geq 2=f_{3}$ gilt. Durch vollständige Induktion erhält man (für $i=0,1,\ldots ,n-1$)

${\begin{aligned}v_{n-i-1}&=q_{n-i}v_{n-i}+v_{n-i+1}\\&\geq v_{n-i}+v_{n-i+1}\\&\geq f_{i+2}+f_{i+1}=f_{i+3}.\end{aligned}}$

Speziell für $i=n-2$ ergibt sich $v=v_{1}\geq f_{n+1}$.

Andererseits gilt $f_{k}\geq \Phi ^{k-2}$ für ganzzahliges $k\geq 2$, wobei $\Phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618$ das Verhältnis des Goldenen Schnitts ist. Dies lässt sich durch vollständige Induktion beweisen, beginnend mit $f_{2}=\Phi ^{0}=1$ und $f_{3}=2>\Phi ^{1}$. Der Induktionsschritt verwendet die Beziehung $\Phi ^{2}=\Phi +1.$

${\begin{aligned}f_{k+1}&=f_{k}+f_{k-1}\\&\geq \Phi ^{k-2}+\Phi ^{k-3}\\&=\Phi ^{k-3}(\Phi +1)\\&=\Phi ^{k-1}.\end{aligned}}$

Die Zahl $n$ der Schritte des euklidischen Algorithmus kann also folgendermaßen abgeschätzt werden:

$v\geq f_{n+1}\geq \Phi ^{n-1},$

$n-1\leq {\frac {\log _{10}v}{\log _{10}\Phi }}<5\log _{10}v.$

Dabei wurde ${\frac {1}{\log _{10}\Phi }}\approx 4{,}78<5$ verwendet.

Ist $k$ die Zahl der Dezimalstellen von $v$, so gilt $v<10^{k}$, also $\log _{10}v<k$. Daraus folgt

$n-1<5k,$

und, weil beide Seiten der Ungleichung ganzzahlig sind,

$n\leq 5k.$

Das ist die Behauptung des Satzes von Lamé.

Als Nebenresultat des Beweises erhält man die Aussage, dass diejenigen Paare $(u,v)$ von natürlichen Zahlen, bei denen der euklidische Algorithmus (für ein gegebenes $v$) die maximale Zahl von Schritten benötigt, Paare aufeinanderfolgender Fibonacci-Zahlen sind.

Weitere Erweiterungen und Verallgemeinerungen

Im Laufe der Jahre wurden verschiedene Erweiterungen und Verallgemeinerungen des Satzes von Lamé entwickelt. Eine bedeutende Erweiterung befasst sich mit der Analyse von Algorithmen zur Berechnung des größten gemeinsamen Teilers in größeren Zahlensystemen, etwa im Rahmen der algebraischen Zahlentheorie oder bei der Berechnung von algebraischen Inversen.

Zusätzlich wurden schnellere Varianten des Euklidischen Algorithmus entwickelt, die auch die Schranke des Satzes von Lamé in bestimmten Fällen überschreiten können, um effizientere Algorithmen zu realisieren. Einige dieser Varianten basieren auf optimierten Methoden wie der schnellen exponentiellen Berechnung oder dem multiplizierten Euklidischen Algorithmus.

Literatur

• Gabriel Lamé: "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes rendus des séances de l'Académie des Sciences (in French). 19: 867–870 (1844)