Kryptologie/Satz von Euler

Aus Wikiversity


Einleitung

Der Satz von Euler ist eine Verallgemeinerung des kleinen Satzes von Fermat. Während der kleine Satz von Fermat nur für Primzahlen gilt, kann der Satz von Euler auf beliebige natürliche Zahlen angewendet werden, die teilerfremd zur Basis sind[1]. Der Satz von Euler ist der zentrale Satz zum Beweis der Korrektheit des RSA-Kryptosystems[2]. Außerdem werden wir ihn nutzen, um einen weiteren Satz für die Korrektheit des RSA-Kryptosystems zu zeigen, nämlich dem chinesischen Restsatz.

Satz von Euler

Größte gemeinsame Teiler, (Satz 1) Eulersche -Funktion

und kleine Satz von Fermat

Größte gemeinsame Teiler
Seien , wobei mindestens eine der beiden Zahlen ungleich Null.

Wir bezeichnen mit als den größten gemeinsamen

Teiler der Zahlen und , falls gilt:

: und

und

: Für alle mit und [3].

Eulersche -Funktion
Für die eulersche -Funktion gilt: [4][5] mit

[6][5].

Satz 1 Eigenschaft der -Funktion bei Primzahlen
Sei prim, dann gilt: [6][7].
Kleiner Satz von Fermat
Für jede Primzahl und jede dazu teilerfremde natürliche Zahl ist

folgende Kongruenz erfüllt: [8][9].

Seien und , dann gilt [1][10].

Bemerkung: Für prime Moduli gilt nach Satz 1 Eigenschaft der Eulerschen -Funktion bei Primzahlen , also geht für diese der Satz von Euler in den kleinen Satz von Fermat über[1].

Beweis Satz von Euler

Teil 1

Wir zeigen zunächst die Aussage: wenn prim, dann gilt mittels vollständiger Induktion nach .

Bemerkung: Bei der vollständigen Induktion wird eine Aussage in der Regel für alle natürlichen Zahlen bewiesen. Dabei beginnt man bei einem Startwert (meist oder ) und zeigt, dass die Aussage für diesen Startwert gilt. Man nennt dies den Induktionsanfang. Anschließend wird während des Induktionsschritts gezeigt, dass wenn die Aussage für eine Zahl gilt, dann gilt sie auch für die nächstgrößere Zahl[11][12].

Seien prim und , dann soll gelten

für .

Eulersche -Funktion, Kongruenz, wichtige Sätze

und der Binomialkoeffizient

Eulersche -Funktion
Für die eulersche -Funktion gilt: [4][5] mit

[6][5].

Kongruenz
Seien und , dann gilt [13].
Satz 1 Eigenschaft der -Funktion bei Primzahlen
Sei prim, dann gilt: [6][7].
Kleiner Satz von Fermat
Für jede Primzahl und jede dazu teilerfremde natürliche Zahl ist

folgende Kongruenz erfüllt: [8][9].

Satz 3 Eigenschaft der -Funktion bei Primzahlen
Seien prim und mit , dann gilt: [6][7].
Binomischer Lehrsatz[14]
Für alle Elemente und eines kommutativen monoiden Rings und für

alle natürlichen Zahlen gilt die Gleichung

.[14][15]

Binomialkoeffizient[14]
Seien , dann gilt:

[14][16]

Wir zeigen nun durch vollständige Induktion, dass die Kongruenz korrekt ist.

Induktionsanfang

Wir beginnen mit .

, für

, nach Satz 1 der Eigenschaft für -Funktionen

Dies ist genau der kleine Satz von Fermat, welchen wir bereits bewiesen haben.

Induktionsvoraussetzung

Wir nehmen an, dass für ein festes mit gilt.

Induktionsbehauptung

Wir wollen zeigen, dass gilt.

Induktionsschritt

Nach der Kongruenz gilt folgende Äquivalenz der Induktionsvoraussetzung:

mit und Satz 3 der eulerschen -Funktion gilt .

Für folgt unter erneuter Verwendung von Satz 3 der eulerschen -Funktion

.

Wir können nun umschreiben:

, da

, nach

Nun kann man den binomischen Lehrsatz anwenden, da es sich bei dem Restklassenring um einen kommutativen Ring handelt, wobei ein Monoid ist (siehe Lernaufgabe).

Also

Betrachten wir nun die Summen

, und getrennt voneinander.

Es gilt

, da jeder der Summanden aus einem Faktoren mit und einem Binomialkoeffizienten besteht und der Faktor immer von teilbar ist und lediglich mit einer natürlichen Zahl (dem zugehörigen Binomialkoeffizienten) multipliziert wird.

Wir müssen nun also nur noch die beiden Summanden und betrachten.

Da , ist .

Es gilt: .

Wir wissen nun also, dass

und nach hinzufügen des Summanden :

.

Wir haben also gezeigt, dass gilt:

und die vollständige Induktion ist abgeschlossen.

Primfaktorzerlegung, Teilerfremdheit, (Multiplikativität für Primzahlen der)

Eulersche -Funktion und Folgerung aus Lemma 4 des

Primfaktorzerlegung
Sei mit , dann ist als Produkt von Primzahlen darstellbar und wir nennen diese

Primfaktorzerlegung. Es gilt mit .

Die Darstellung ist, abgesehen von der Reihenfolge der Faktoren, eindeutig[17].

Teilerfremdheit
Zwei ganze Zahlen und , wobei mindestens einer der beiden Zahlen ungleich Null ist,

heißen teilerfremd, wenn [18]. Betrachten wir mehr als zwei Zahlen, dann

nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander

teilerfremd sind[19][18].

Eulersche -Funktion
Für die eulersche -Funktion gilt: [4][5] mit

[6][5].

Multiplikativität der eulerschen -Funktion für Primzahlen
Seien und prim und , dann gilt [4][7].
Folgerung aus Lemma 4 des
Gilt und mit , dann folgt [20].

Teil 2

Nun wählen wir eine Zahl mit und folgender Primfaktorzerlegung:

.

Da und teilerfremd sind, kann auch keiner der Primfaktoren mit ein Teiler von sein.

Wir erhalten die Kongruenz:

mit .

Nun nutzen wir die Multiplikativität der eulerschen -Funktion:

, also ist jeder Faktor ein Teiler von .

Daher gilt nicht nur , sondern auch

mit .

Da die Primfaktorpotenzen paarweise teilerfremd sind, gilt nach der Folgerung aus Lemma 4 des ggT :

,

und da

die Primfaktorzerlegung von ist, gilt

.

Wir haben somit den Satz von Euler bewiesen■[21]

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
8: Korrektheit des RSA-Verschlüsselungsverfahrens
Vorherige Lerneinheit Aktuelle Lerneinheit Empfohlene Lerneinheit
8: Korrektheit des RSA-Verschlüsselungsverfahrens 8.1: Satz von Euler 8.2: Chinesischer Restsatz

Literatur

  1. 1,0 1,1 1,2 „Satz von Euler“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 27. März 2019, 10:16 UTC. URL: https://de.wikipedia.org/w/index.php?title=Satz_von_Euler&oldid=186980132 (Abgerufen: 25. November 2019, 10:25 UTC; Formulierung verändert)
  2. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 123.
  3. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.
  4. 4,0 4,1 4,2 4,3 Kryptologie - Mathematische Vertiefung (PH Freiburg SS 2017). (5. Dezember 2019). Wikiversity, . Abgerufen am 8. Januar 2020, 12:14 von https://de.wikiversity.org/w/index.php?title=Kryptologie_-_Mathematische_Vertiefung_(PH_Freiburg_SS_2017)&oldid=605650. (Formulierung verändert)
  5. 5,0 5,1 5,2 5,3 5,4 5,5 Stroth, G., & Waldecker, R. (2019). Elementare Algebra und Zahlentheorie (2. Aufl.). Birkhäuser Basel. S. 77.
  6. 6,0 6,1 6,2 6,3 6,4 6,5 Seite „Eulersche Phi-Funktion“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 24. August 2019, 16:52 UTC. URL: https://de.wikipedia.org/w/index.php?title=Eulersche_Phi-Funktion&oldid=191644019 (Abgerufen: 7. Januar 2020, 09:45 UTC; Formulierung verändert)
  7. 7,0 7,1 7,2 7,3 Wätjen, D. (2018). Kryptographie: Grundlagen, Algorithmen, Protokolle. Springer-Verlag. S. 42.
  8. 8,0 8,1 Seite „Fermatscher Primzahltest“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 7. März 2017, 21:10 UTC. URL: https://de.wikipedia.org/w/index.php?title=Fermatscher_Primzahltest&oldid=163373890 (Abgerufen: 23. Dezember 2019, 11:46 UTC; Formulierung verändert)
  9. 9,0 9,1 Oswald, N., & Steuding, J. (2015). Elementare Zahlentheorie: Ein sanfter Einstieg in die höhere Mathematik. Springer Spektrum. S. 129.
  10. Euler, L. (1763). Theoremata arithmetica nova methodo demonstrata. 8 (S. 74–104). S. 102.
  11. Seite „Vollständige Induktion“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 20. Dezember 2019, 06:00 UTC. URL: https://de.wikipedia.org/w/index.php?title=Vollst%C3%A4ndige_Induktion&oldid=195068438 (Abgerufen: 12. Januar 2020, 09:16 UTC; Formulierung verändert)
  12. Schäfer, W., Georgi, K., & Trippler, G. (1999). Mathematik-Vorkurs—Übungs- und Arbeitsbuch für Studienanfänger. Vieweg+Teubner. S. 102.
  13. Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
  14. 14,0 14,1 14,2 14,3 Seite „Binomischer Lehrsatz“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 28. Dezember 2019, 11:23 UTC. URL: https://de.wikipedia.org/w/index.php?title=Binomischer_Lehrsatz&oldid=195279006 (Abgerufen: 10. Januar 2020, 14:31 UTC; Formulierung verändert)
  15. Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 44.
  16. Witt, K.-U. (2001). Binomialkoeffizienten. In K.-U. Witt (Hrsg.), Algebraische Grundlagen der Informatik: Zahlen—Strukturen—Codierung—Verschlüsselung (S. 145–148). Vieweg+Teubner Verlag. S. 145.
  17. Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 66.
  18. 18,0 18,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.
  19. Seite „Teilerfremdheit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. September 2019, 13:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilerfremdheit&oldid=192615323 (Abgerufen: 10. Januar 2020, 13:56 UTC)
  20. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. 27.
  21. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag, S. 153f.