<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="de">
	<id>https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=Satz_von_Euler</id>
	<title>Satz von Euler - Versionsgeschichte</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=Satz_von_Euler"/>
	<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Satz_von_Euler&amp;action=history"/>
	<updated>2026-11-16T00:43:10Z</updated>
	<subtitle>Versionsgeschichte dieser Seite in FLBK-Wiki</subtitle>
	<generator>MediaWiki 1.46.2</generator>
	<entry>
		<id>https://wiki.flbk-hamm.de/index.php?title=Satz_von_Euler&amp;diff=3214&amp;oldid=prev</id>
		<title>Flbkwikiadmin: Die Seite wurde neu angelegt: „Warum liefert das Entschlüsseln beim RSA-Verfahren wieder den Klartext? Die Antwort gibt ein Satz, den Leonhard Euler im 18. Jahrhundert bewiesen hat.  ==Definition== Der &#039;&#039;&#039;Satz von Euler&#039;&#039;&#039; lautet: Für alle natürlichen Zahlen &lt;math&gt;a&lt;/math&gt; und &lt;math&gt;n&lt;/math&gt;, die teilerfremd sind, gilt  :&lt;math&gt;a^{\varphi(n)} \equiv 1 \pmod{n}&lt;/math&gt;  Dabei ist &lt;math&gt;\varphi(n)&lt;/math&gt; der Wert der eulerschen φ-Funktio…“</title>
		<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Satz_von_Euler&amp;diff=3214&amp;oldid=prev"/>
		<updated>2026-11-15T06:51:44Z</updated>

		<summary type="html">&lt;p&gt;Die Seite wurde neu angelegt: „Warum liefert das Entschlüsseln beim &lt;a href=&quot;/RSA-Verfahren&quot; title=&quot;RSA-Verfahren&quot;&gt;RSA-Verfahren&lt;/a&gt; wieder den Klartext? Die Antwort gibt ein Satz, den Leonhard Euler im 18. Jahrhundert bewiesen hat.  ==Definition== Der &amp;#039;&amp;#039;&amp;#039;Satz von Euler&amp;#039;&amp;#039;&amp;#039; lautet: Für alle natürlichen Zahlen &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt;, die &lt;a href=&quot;/Euklidischer_Algorithmus#Teilerfremdheit&quot; title=&quot;Euklidischer Algorithmus&quot;&gt;teilerfremd&lt;/a&gt; sind, gilt  :&amp;lt;math&amp;gt;a^{\varphi(n)} \equiv 1 \pmod{n}&amp;lt;/math&amp;gt;  Dabei ist &amp;lt;math&amp;gt;\varphi(n)&amp;lt;/math&amp;gt; der Wert der eulerschen φ-Funktio…“&lt;/p&gt;
&lt;p&gt;&lt;b&gt;Neue Seite&lt;/b&gt;&lt;/p&gt;&lt;div&gt;Warum liefert das Entschlüsseln beim [[RSA-Verfahren]] wieder den Klartext? Die Antwort gibt ein Satz, den Leonhard Euler im 18. Jahrhundert bewiesen hat.&lt;br /&gt;
&lt;br /&gt;
==Definition==&lt;br /&gt;
Der &amp;#039;&amp;#039;&amp;#039;Satz von Euler&amp;#039;&amp;#039;&amp;#039; lautet: Für alle natürlichen Zahlen &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt;, die [[Euklidischer Algorithmus#Teilerfremdheit|teilerfremd]] sind, gilt&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;a^{\varphi(n)} \equiv 1 \pmod{n}&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Dabei ist &amp;lt;math&amp;gt;\varphi(n)&amp;lt;/math&amp;gt; der Wert der eulerschen φ-Funktion. In Worten: Potenziert man &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;\varphi(n)&amp;lt;/math&amp;gt;, bleibt bei der Division durch &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; der Rest 1. Die Schreibweise mit &amp;lt;math&amp;gt;\equiv&amp;lt;/math&amp;gt; erklärt der Artikel [[Modulo#Kongruenz|Modulo]].&lt;br /&gt;
&lt;br /&gt;
==Eulersche φ-Funktion==&lt;br /&gt;
Die &amp;#039;&amp;#039;&amp;#039;eulersche φ-Funktion&amp;#039;&amp;#039;&amp;#039; (gesprochen: Phi-Funktion) gibt zu einer natürlichen Zahl &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; an, wie viele der Zahlen von 1 bis &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; zu &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; teilerfremd sind.&lt;br /&gt;
&lt;br /&gt;
* Für eine Primzahl &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; gilt &amp;lt;math&amp;gt;\varphi(p) = p - 1&amp;lt;/math&amp;gt;, denn alle Zahlen von 1 bis &amp;lt;math&amp;gt;p - 1&amp;lt;/math&amp;gt; sind zu &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; teilerfremd.&lt;br /&gt;
* Für das Produkt zweier verschiedener Primzahlen &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;q&amp;lt;/math&amp;gt; gilt&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;\varphi(p \cdot q) = (p - 1) \cdot (q - 1)&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Begründung: Von den &amp;lt;math&amp;gt;p \cdot q&amp;lt;/math&amp;gt; Zahlen von 1 bis &amp;lt;math&amp;gt;p \cdot q&amp;lt;/math&amp;gt; sind genau die Vielfachen von &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; und die Vielfachen von &amp;lt;math&amp;gt;q&amp;lt;/math&amp;gt; nicht teilerfremd zu &amp;lt;math&amp;gt;p \cdot q&amp;lt;/math&amp;gt;. Es gibt &amp;lt;math&amp;gt;q&amp;lt;/math&amp;gt; Vielfache von &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; Vielfache von &amp;lt;math&amp;gt;q&amp;lt;/math&amp;gt;. Die Zahl &amp;lt;math&amp;gt;p \cdot q&amp;lt;/math&amp;gt; selbst gehört zu beiden Gruppen und wurde doppelt gezählt. Übrig bleiben&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;p \cdot q - q - p + 1 = (p - 1) \cdot (q - 1)&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Zahlen.&lt;br /&gt;
&lt;br /&gt;
Wer &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;q&amp;lt;/math&amp;gt; kennt, berechnet &amp;lt;math&amp;gt;\varphi(p \cdot q)&amp;lt;/math&amp;gt; also mit einer einzigen Multiplikation. Wer nur das Produkt kennt, muss es erst in seine Primfaktoren zerlegen (siehe [[Primfaktorzerlegung]]).&lt;br /&gt;
&lt;br /&gt;
==Bedeutung für RSA==&lt;br /&gt;
Beim RSA-Verfahren ist &amp;lt;math&amp;gt;N = p \cdot q&amp;lt;/math&amp;gt;, und die Zahlen &amp;lt;math&amp;gt;e&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;d&amp;lt;/math&amp;gt; der beiden Schlüssel erfüllen &amp;lt;math&amp;gt;e \cdot d \equiv 1 \pmod{\varphi(N)}&amp;lt;/math&amp;gt;. Es gibt also eine ganze Zahl &amp;lt;math&amp;gt;k&amp;lt;/math&amp;gt; mit&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;e \cdot d = 1 + k \cdot \varphi(N)&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Verschlüsselt man eine Nachricht &amp;lt;math&amp;gt;m&amp;lt;/math&amp;gt; und entschlüsselt das Ergebnis, wird &amp;lt;math&amp;gt;m&amp;lt;/math&amp;gt; insgesamt mit &amp;lt;math&amp;gt;e \cdot d&amp;lt;/math&amp;gt; potenziert. Mit dem Satz von Euler folgt:&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;m^{e \cdot d} = m^{1 + k \cdot \varphi(N)} = m \cdot \left(m^{\varphi(N)}\right)^k \equiv m \cdot 1^k = m \pmod{N}&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Das Entschlüsseln liefert also wieder die Nachricht &amp;lt;math&amp;gt;m&amp;lt;/math&amp;gt;. Der Satz von Euler setzt voraus, dass &amp;lt;math&amp;gt;m&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;N&amp;lt;/math&amp;gt; teilerfremd sind. Für einen RSA-Modul lässt sich zeigen, dass die Gleichung auch für die übrigen Nachrichten gilt.&lt;br /&gt;
&lt;br /&gt;
Allgemein folgt aus dem Satz: Beim Rechnen modulo &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; darf man im Exponenten Vielfache von &amp;lt;math&amp;gt;\varphi(n)&amp;lt;/math&amp;gt; weglassen, solange die Basis zu &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; teilerfremd ist.&lt;br /&gt;
&lt;br /&gt;
==Beispiele==&lt;br /&gt;
===φ durch Abzählen und mit der Formel bestimmen===&lt;br /&gt;
* &amp;lt;math&amp;gt;n = 9&amp;lt;/math&amp;gt;: Von den Zahlen 1 bis 9 sind 1, 2, 4, 5, 7, 8 zu 9 teilerfremd. Das sind 6 Zahlen, also &amp;lt;math&amp;gt;\varphi(9) = 6&amp;lt;/math&amp;gt;.&lt;br /&gt;
* &amp;lt;math&amp;gt;n = 14 = 2 \cdot 7&amp;lt;/math&amp;gt;: Hier hilft die Formel für das Produkt zweier Primzahlen: &amp;lt;math&amp;gt;\varphi(14) = (2 - 1) \cdot (7 - 1) = 6&amp;lt;/math&amp;gt;. Zur Kontrolle: Teilerfremd zu 14 sind 1, 3, 5, 9, 11, 13.&lt;br /&gt;
&lt;br /&gt;
===Satz von Euler nachrechnen===&lt;br /&gt;
* &amp;lt;math&amp;gt;a = 2&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;n = 9&amp;lt;/math&amp;gt;: &amp;lt;math&amp;gt;2^{6} = 64 = 7 \cdot 9 + 1&amp;lt;/math&amp;gt;&lt;br /&gt;
* &amp;lt;math&amp;gt;a = 3&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;n = 14&amp;lt;/math&amp;gt;: &amp;lt;math&amp;gt;3^{6} = 729 = 52 \cdot 14 + 1&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
===Großen Exponenten verkleinern===&lt;br /&gt;
Gesucht ist &amp;lt;math&amp;gt;3^{20} \bmod 14&amp;lt;/math&amp;gt;. Wegen &amp;lt;math&amp;gt;3^{6} \equiv 1 \pmod{14}&amp;lt;/math&amp;gt; darf man im Exponenten Vielfache von 6 weglassen:&lt;br /&gt;
:&amp;lt;math&amp;gt;3^{20} = 3^{3 \cdot 6 + 2} = (3^{6})^{3} \cdot 3^{2} \equiv 1 \cdot 9 = 9 \pmod{14}&amp;lt;/math&amp;gt;&lt;br /&gt;
Also ist &amp;lt;math&amp;gt;3^{20} \bmod 14 = 9&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
[[Kategorie:Kryptologie]]&lt;br /&gt;
[[Kategorie:Mathematik]]&lt;br /&gt;
[[Kategorie:AHR I Informatik LK]]&lt;/div&gt;</summary>
		<author><name>Flbkwikiadmin</name></author>
	</entry>
</feed>