Hauptmenü öffnen

Kleiner fermatscher Satz

mathematischer Satz
(Weitergeleitet von Kleiner Fermatscher Satz)

Der kleine fermatsche Satz, kurz „der kleine Fermat“, ist ein Lehrsatz der Zahlentheorie. Er macht eine Aussage über die Eigenschaften von Primzahlen und wurde im 17. Jahrhundert von Pierre de Fermat aufgestellt. Der Satz beschreibt die allgemeingültige Kongruenz:

wobei eine ganze Zahl und eine Primzahl ist (die weitere Symbolik wird im Artikel Kongruenz beschrieben).

Falls kein Vielfaches von ist, kann man das Resultat in die häufig benutzte Form

bringen, da dann das multiplikative Inverse modulo existiert.

BeweisBearbeiten

Der Satz kann mit Induktion über   bewiesen werden oder als Spezialfall des Satzes von Lagrange aus der Gruppentheorie aufgefasst werden. Dieser sagt, dass jedes Gruppenelement potenziert mit der (endlichen) Gruppenordnung das Einselement ergibt.

Siehe: Beweise des kleinen fermatschen Satzes im Beweisarchiv

Folgerung durch EulerBearbeiten

Die 3. Binomische Formel besagt:

 

Sei nun   eine ungerade Primzahl und   eine beliebige ganze Zahl. Falls   kein Teiler von   ist, folgt aus dem kleinen Fermatschen Satz, dass die rechte Seite der Gleichung ein Vielfaches der Primzahl   ist. Damit ist einer der Faktoren ein Vielfaches von  .

Es gilt folglich

 

Diese Folgerung wird Leonhard Euler zugeschrieben.

VerallgemeinerungBearbeiten

Man kann den kleinen Fermatschen Satz zum Satz von Euler verallgemeinern.

Für zwei teilerfremde Zahlen   und   gilt

 

wobei   die eulersche φ-Funktion bezeichnet. Diese liefert die Anzahl der Zahlen zwischen   und  , welche teilerfremd zu   sind. Ist   eine Primzahl, so ist  , so dass man Fermats kleinen Satz als Spezialfall erhält.

Anwendung als PrimzahlentestBearbeiten

Nach dem kleinen fermatschen Satz gilt für jede Primzahl   und jedes dazu teilerfremde  :

 

mit einer ganzen Zahl  . Diese Beziehung kann auch für eine zusammengesetzte Zahl   und eine Zahl   mit   zutreffen. Dies ist jedoch zumindest für große Zahlen   sehr selten. Findet man Zahlen   mit dieser Eigenschaft für eine zusammengesetzte Zahl  , kann dies zur Faktorisierung der Zahl   genutzt werden, da die Faktoren auf der linken Seite dann mit einer Wahrscheinlichkeit von 50 % echte Teiler von   liefern.

Für eine Zahl   mit 100 oder mehr Stellen ist eine Primfaktorzerlegung jedoch nur mit effizienteren Verfahren wie dem quadratischen Sieb möglich. Der Satz kann daher auch in seiner Umkehrung benutzt werden, um mit hoher Verlässlichkeit zu beurteilen, ob eine Zahl eine Primzahl ist. Bei großen Zahlen mit über 100 Stellen ist praktisch nicht daran zu zweifeln, dass   eine Primzahl ist, falls die Gleichung für ein   mit   gilt. (siehe: Fermatscher Primzahltest)

Für einen exakten Beweis wäre allerdings die Prüfung aller Werte   notwendig, so dass die Probedivision in diesem Fall effizienter ist. Es ist nicht bekannt, dass eine 100-stellige oder größere Zahl auf diese Weise faktorisiert werden konnte.

Für einige spezielle Zahlen können solche Ausnahmen allerdings häufiger gefunden werden.

Shor-AlgorithmusBearbeiten

Es sei   das Produkt zweier großer Primzahlen   und  . Wir betrachten eine Zahl   mit  . Wir wissen, dass für den Exponenten  

 

gilt.

Es stellt sich die Frage, ob diese Gleichung bereits für kleinere Exponenten erfüllt ist. Der Quantenteil des Shor-Algorithmus zur Faktorisierung großer Zahlen dient der Berechnung der kleinsten Zahl  , für die diese Gleichung gilt. Der klassische Teil dieses Algorithmus kann leicht auf nahezu jedem Computer ausgeführt werden.

Wenn man die Potenzen einer Zahl bezüglich der Modulo-Operation betrachtet, wiederholen diese sich in Zyklen. Dies ist unvermeidlich, da nur die Werte   angenommen werden können. Wir betrachten dies am Beispiel kleinerer Zahlen.

Wir können uns auf die Betrachtung von Primzahlen beschränken, da sich die minimale Zyklenlänge für das Produkt aus dem kleinsten gemeinsamen Vielfachen der Zyklenlängen für die Faktoren ergibt.

Beispiel mit p=7
n            
0 1 1 1 1 1 1
1 2 2 3 3 5 5
2 4 4 9 2 25 4
3 8 1 27 6 125 6
4 16 2 81 4 625 2
5 32 4 243 5 3125 3
6 64 1 729 1 15625 1
7 128 2 2187 3 78125 5

und so weiter. In der Tabelle wurde   aus   berechnet. Um größere Zahlen zu vermeiden, kann man das Ergebnis einfacher aus   berechnen.

In diesem Beispiel mit   ergibt sich für   folgender Zyklus der Werte  

  • 1, 2, 4, 1, 2, 4, 1, 2, …

Für   ergibt sich

  • 1, 3, 2, 6, 4, 5, 1, 3, …

Für alle drei Basen 2, 3 und 5 gilt zur Zahl 7

  für alle  

oder allgemein

 

für alle   und alle natürlichen a, für die gilt  . Dies ist eine unmittelbare Folge des kleinen Satzes von Fermat.

Am Beispiel der Modulo-Werte für   sieht man, dass sich der Algorithmus verkürzen lässt, wenn der Zyklus kürzer ist. Da  , ist auch  , d. h.  . Für größere Zahlen lässt sich so Arbeit einsparen.

Weitere VereinfachungBearbeiten

Hat   die Form   ergeben sich weitere Vereinfachungen der Berechnung. Dies wird hier am Beispiel   verdeutlicht.

Beispiel mit p=17
n 1 2 4 8 16 32
  2 4 16 1 1 1
  3 9 13 16 1 1
  5 8 13 16 1 1
  7 15 4 16 1 1
  11 2 4 16 1 1
  13 16 1 1 1 1

Da   ein Vielfaches der Zyklenlänge ist, kommen für   nur die Zahlen   in Betracht, was den Rechenaufwand vor allem für sehr große   deutlich reduzieren kann. Noch weniger Arbeit macht der Fall

 ,

da das Ergebnis dann für die nächste Potenz von 2 schon als 1 feststeht.

LiteraturBearbeiten

  • Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen. 4. Auflage. S. 657

WeblinksBearbeiten