Russen, Chinesen, DDRler und T

20/02/2013 - 19:07 von D Orbital | Report spam
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 allgemein gültige Kongruenz:

a^p \equiv a\,(\mathrm{mod}\,p),

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

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

a^{p-1} \equiv 1\,(\mathrm{mod}\,p)

bringen.
Inhaltsverzeichnis

1 Beweis
2 Folgerung durch Euler
3 Verallgemeinerung
4 Anwendung als Primzahlentest
4.1 Shor-Algorithmus
4.1.1 Weitere Vereinfachung
5 Weblinks
6 Literatur

Beweis

Der Satz kann mit Induktion über a 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 Euler

Die 3. Binomische Formel besagt:

(a^{\frac{p-1}{2}}-1) \cdot (a^{\frac{p-1}{2}}+1) = a^{p-1} - 1

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

Es gilt folglich

a^{\frac{p-1}{2}}\equiv \pm 1\,(\mathrm{mod}\,p)

Diese Folgerung wird Leonhard Euler zugeschrieben.
Verallgemeinerung

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

Für zwei teilerfremde Zahlen n und a gilt

a^{\varphi (n)} \equiv 1\,(\mathrm{mod}\,n),

wobei \varphi(n) die eulersche φ-Funktion bezeichnet. Diese liefert die Anzahl der Zahlen zwischen 1 und n-1, welche teilerfremd zu n sind. Ist n eine Primzahl, so ist \varphi(n)=n-1, so dass man Fermats kleinen Satz als Spezialfall erhàlt.
Anwendung als Primzahlentest

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

(a^{\frac{p-1}{2}}-1) \cdot (a^{\frac{p-1}{2}}+1) = a^{p-1} - 1 = k \cdot p

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

Für eine Zahl p 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 Sicherheit zu entscheiden, ob eine Zahl eine Primzahl ist. Bei großen Zahlen mit über 100 Stellen ist praktisch nicht daran zu zweifeln, dass p eine Primzahl ist, falls die Gleichung für ein a mit 1 < a < p gilt. (siehe: Fermatscher Primzahltest)

Für einen exakten Beweis wàre allerdings die Prüfung aller Werte 1 < a < p-1 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-Algorithmus

Es sei n das Produkt zweier großer Primzahlen p und q. Wir betrachten eine Zahl x mit 1<x<n. Wir wissen, dass für den Exponenten r = \varphi(n) = (p-1) \cdot (q-1)

x^r \equiv 1 \mod n

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 r, 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 1, 2, 3, ..., n-1 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.
 

Lesen sie die antworten

#1 D Orbital
01/03/2013 - 16:14 | Warnen spam
Am Mittwoch, 20. Februar 2013 19:07:21 UTC+1 schrieb D Orbital:
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 allgemein gültige Kongruenz:



a^p \equiv a\,(\mathrm{mod}\,p),



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



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



a^{p-1} \equiv 1\,(\mathrm{mod}\,p)



bringen.

Inhaltsverzeichnis



1 Beweis

2 Folgerung durch Euler

3 Verallgemeinerung

4 Anwendung als Primzahlentest

4.1 Shor-Algorithmus

4.1.1 Weitere Vereinfachung

5 Weblinks

6 Literatur



Beweis



Der Satz kann mit Induktion über a 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 Euler



Die 3. Binomische Formel besagt:



(a^{\frac{p-1}{2}}-1) \cdot (a^{\frac{p-1}{2}}+1) = a^{p-1} - 1



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



Es gilt folglich



a^{\frac{p-1}{2}}\equiv \pm 1\,(\mathrm{mod}\,p)



Diese Folgerung wird Leonhard Euler zugeschrieben.

Verallgemeinerung



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



Für zwei teilerfremde Zahlen n und a gilt



a^{\varphi (n)} \equiv 1\,(\mathrm{mod}\,n),



wobei \varphi(n) die eulersche φ-Funktion bezeichnet. Diese liefert die Anzahl der Zahlen zwischen 1 und n-1, welche teilerfremd zu n sind. Ist n eine Primzahl, so ist \varphi(n)=n-1, so dass man Fermats kleinen Satz als Spezialfall erhàlt.

Anwendung als Primzahlentest



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



(a^{\frac{p-1}{2}}-1) \cdot (a^{\frac{p-1}{2}}+1) = a^{p-1} - 1 = k \cdot p



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



Für eine Zahl p 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 Sicherheit zu entscheiden, ob eine Zahl eine Primzahl ist. Bei großen Zahlen mit über 100 Stellen ist praktisch nicht daran zu zweifeln, dass p eine Primzahl ist, falls die Gleichung für ein a mit 1 < a < p gilt. (siehe: Fermatscher Primzahltest)



Für einen exakten Beweis wàre allerdings die Prüfung aller Werte 1 < a < p-1 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-Algorithmus



Es sei n das Produkt zweier großer Primzahlen p und q. Wir betrachten eine Zahl x mit 1<x<n. Wir wissen, dass für den Exponenten r = \varphi(n) = (p-1) \cdot (q-1)



x^r \equiv 1 \mod n



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 r, 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 1, 2, 3, ..., n-1 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.



Mit " Türken " meine ich die Hausmeister.

Ähnliche fragen