From 606f5d0570cdaafaa85aef2509fce40286e0babb Mon Sep 17 00:00:00 2001 From: Peter Schaefer Date: Mon, 2 Jul 2012 19:33:58 +0200 Subject: [PATCH] =?utf8?q?Vorlesung=20erg=C3=A4nzt?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- Vorlesung.tex | 645 +++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 644 insertions(+), 1 deletion(-) diff --git a/Vorlesung.tex b/Vorlesung.tex index 26ee42f..0dfa713 100644 --- a/Vorlesung.tex +++ b/Vorlesung.tex @@ -895,6 +895,649 @@ Beim Empfang der Nachricht geht Alice wie folgt vor: \end{bem} \begin{bem}[Bemerkung zu Knapsack-Problem] -Sind die Gewichte beispielsweise (alle) Potenzen von $2$ und kommt jedes Item höchstens einmal vor, so erhält man aus der Binärdarstellung die (eindeutige) Lösung. +Sind die Gewichte beispielsweise (alle) Potenzen von $2$ und kommt jedes Item höchstens einmal vor, so erhält man aus der Binärdarstellung die (eindeutige) Lösung. Ist daher eine Folge super-increasing, ist die Aufspaltung der Summe leicht. \\ +Sei also $b_{1}, b_{2}, b_{3}, \ldots$ super-increasing. Definiere für $m > b_{1}+\ldots+b_{n}$: +\begin{equation} + a_{i}:= w \cdot b_{\pi(i)} \mod m +\end{equation} +Geheimer Schlüssel: $[\pi,w,m]$. \\ +Öffentlicher Schlüssel: $[a_{1}, \ldots, a_{n}]$ \\ +Ist nun $x=x_{1}x_{2}\cdots x_{n} \in \lbrace 0,1 \rbrace^{n}$ gegeben, so bilde ($a\cdot x$ ist hier als inneres Produkt zu interpretieren!): +\begin{equation} + s:=a\cdot x=a_{1}x_{1}+a_{2}x_{2}+\ldots+a_{n}x_{n} \mod m \textsl{ ist das Chiffrat} +\end{equation} +Angenommen: $w^{\prime}w \equiv 1 \mod m$, d.h. $w^{\prime}$ ist das Inverse zu $w \mod m$. Dann gilt +\begin{equation} + s^{\prime}=w^{\prime} s \equiv b_{\pi(1)}x_{1}+b_{\pi(2)}x_{2}+\ldots+b_{\pi(n)}x_{n} +\end{equation} +siehe Skript auf algebra.tuwien.ac.at +\end{bem} + +\begin{bem} + Es gibt Chuer-Rivest-Variante, z.B.: LLL-Verfahren. +\end{bem} + +\begin{bem}[Bemerkung zu Seite 18] + Es gilt + \begin{equation} + de=1+k \cdot \lcm(p-1,q-1), + \end{equation} +weil $ed \equiv 1 \mod n$. +\end{bem} + +% VO 16.5.2012 +\begin{proof}[Beweis zu Satz $1.1$, Seite $18$] + Zeige zuerst mit vollständiger Induktion nach $k$, dass gilt + \begin{equation} + a^{1+k\cdot (p-1)}\equiv a \mod p + \end{equation} +$k=0$ ist klar. \\ +$k \rightarrow k+1$: +\begin{subequations} + \begin{align} + a^{1+(k+1)(p-1)} \equiv a^{p+k(p-1)} \equiv \underbrace{a^{p}}_{\equiv a \mod p (*)} \cdot a^{k(p-1)} \equiv a^{1} \cdot a^{k(p-1)} \stackrel{\textsl{IV}} \equiv a \mod p + \end{align} +\end{subequations} +$(*)$ folgt für $p \nmid a$ aus $a^{(p-1)} \equiv 1 \mod p$ aus dem kleinen Fermat, und ist für $p \mid a$, d.h. $a \equiv 0 \mod p$ trivial. \\ +Analog für $q$: $a^{1+k(q-1)} \equiv a \mod q$. \\ +Und damit auch für $a^{1+k \cdot \lcm(p-1,q-1)} \equiv a \mod p / \mod q$, woraus wg $n=pq=\lcm(p,q)$ die Behauptung aus dem Chinesischen Restsatz folgt. \\ +Dieser Satz gilt auch für Carmichaelzahlen, welche auch die Bedingung $(*)$ erfüllen. +\end{proof} + +\begin{bem}[Bemerkung zu den Fixpunkten] + Man erhält das folgende System von Kongruenzen: + \begin{equation} + \begin{cases} + m^{e} \equiv m \mod p \\ m^{e} \equiv m \mod q + \end{cases} + \end{equation} +Es sind $0,\pm 1 \mod p$ mindestens Lösungen. Es sind $0,\pm 1 \mod q$ mindestens Lösungen. Nach dem Chinesischen Restsatz erhält man daraus $9$ Lösungen $\mod n$. +\end{bem} + +\begin{bem} + Hat $f$ eine kleine Ordnung in der Permutationsgruppe, d.h. $f^{k}(m)=m$ für ein ``kleines'' $k$, so betrachte man + \begin{equation} + f^{(k)}(c)=f(f(\cdots(f(c))))=c + \end{equation} +und man erhält sofort $m=f^{(k-1)}(c)$. +\end{bem} + +\begin{proof}[Beweis zu Satz $1.2$, Seite $19$] + \begin{subequations} + \begin{align} + \left( \pm V_{\frac{r+1}{2}} \right)^{2}=\left( \alpha^{\frac{r+1}{2}} + \beta^{\frac{r+1}{2}} \right)^{2} \stackrel{\textsl{1.Binom.Formel}} = \\ + = \alpha^{r+1} + \beta^{r+1} + 2 \left( \alpha \beta \right)^{\frac{r+1}{2}} = \alpha \alpha^{r} + \beta \beta^{r} + 2 \left( \alpha \beta \right)^{\frac{r-1}{2}} \left( \alpha \beta \right) = \\ +\stackrel{*} = \alpha \beta + \alpha \beta + 2 a^{\frac{r+1}{2}} \left( \alpha \beta \right) \stackrel{**} = \\ += 4 \alpha \beta = 4 Q = 4 a \mod r \\ +\implies \left( \pm \frac{V_{\frac{r+1}{2}}}{2} \right)^{2} \equiv a \mod r + \end{align} + \end{subequations} +@(*): es gilt $a^{r} \equiv \beta \mod r$, $\beta^{r} \equiv \alpha \mod r$\\ +@(**): $a^{\frac{r+1}{2}} \equiv \left( \frac{a}{r} \right) \mod r \equiv 1 \mod r$. Weiters gilt $\alpha \beta=Q \stackrel{\textsl{Vs.}} = a$. \\ +Man beachte, das Inverse von $2 \mod r$ gemeint ist, $r$ ist eine Primzahl, d.h. $\gcd(2,r)=1$, daher ist $2$ invertierbar: +\begin{equation} + \frac{1}{2}=2^{-1}=\frac{1+r}{2} \mod r +\end{equation} +\end{proof} + +\begin{bem}[Bemerkung zu Rabin-Variante] + Man betrachte das System: + \begin{equation} + \begin{cases} + \left( \pm s \right)^{2} \equiv c \mod n \\ \left( \pm t \right)^{2} \equiv c \mod n + \end{cases} + \end{equation} +Daher betrachte: +\begin{equation} + \lbrace \gcd(c+s,n), \gcd(c-s,n), \gcd(c+t,n),\gcd(c-t,n) \rbrace = \lbrace 1,p,q,n \rbrace +\end{equation} +\end{bem} + +\begin{bem}[Bemerkung zu ElGamal] +Sei $m$ das quellencodierte Element von $G$. Verschlüsselung: $(g^{k},m \cdot (g^{a})^{k} )=c=(c_{1},c_{2})$. \\ +Der Empfänger: $m=c_{2} \cdot c_{1}^{-1} = m \cdot g^{ak} (g^{k})^{(-a)} = m$. \\ +In der Gruppe $(\Z,+)$ ist das dlp ganz (!) leicht zu lösen: +\begin{equation} + g^{a}=a\cdot g=\underbrace{g+g+g+g+g+g+g}_{\textsl{a-mal}} = =h +\end{equation} +Division durch $a$ liefert Lösung. \\ +Analog für $(\Z_{n},+)$. $g^{a} \equiv a g \equiv h \mod n \Rightarrow a \equiv g^{-1}h \mod n$, falls $\gcd(g,n)=1$. \\ +Aus Erfahrung ist ``schwer'': $G=(\Z_{p}^{*},\cdot), p \in \P$ groß, $\vert p \vert \approx 1024$ bit. \\ +Bei $G=E(\Z_{p}),p \in \P$ reicht schon $p \approx 2^{160}$, d.h. ein weitaus kleinere Bitanzahl. +\end{bem} + +\begin{bem} + Streng genommen sind die hier betrachteten Tests eigentlich ``Zusammengesetztheitstests'', da falls ein Test nicht bestanden wird sicher ist, dass die Zahl zusammengesetzt ist. Wird der Test bestanden, bleibt eine kleine Irrtumswahrscheinlichkeit. +\end{bem} + +\begin{bem}[Satz von Wilson (oB)] + \begin{equation} + p > 1 \in \P \Leftrightarrow (p-1)! \equiv -1 \mod p + \end{equation} +\end{bem} + +\begin{bem}[Beispiel zu Satz von Wilson] + $p=11: (p-1)! \equiv -1 \mod 11$. \\ +Problem: Faktorielle wachsen stark. +\end{bem} + +\begin{proof}[Beweis zu Satz $2.2$] +Sei +\begin{equation} + U:=\lbrace \bar{a} \in \Z_{N}^{*} \mid \bar{a}^{N-1} \equiv 1 \mod N \rbrace \subseteq \Z_{N}^{*} +\end{equation} + Für eine endliche (Teil-)Menge folgt aus ihrer Abgeschlossenheit schon, dass sie eine Untergruppe ist (nach dem kleinen Satz von Fermat folgt die Existenz eines Inversen). Daher + \begin{subequations} + \begin{align} + \bar{a}_{1},\bar{a}_{2} \in U \Rightarrow \bar{a}_{1}^{N-1} \equiv 1 \mod N \land \bar{a}_{2}^{N-1} \equiv 1 \mod N \\ +\Rightarrow \left( \bar{a}_{1} \bar{a}_{2} \right)^{N-1} \equiv 1 \mod N \\ +\Rightarrow \bar{a}_{1} \cdot \bar{a}_{2} = \bar{a_{1}a_{2}} + \end{align} + \end{subequations} +\end{proof} + +\begin{bem} + Aus $a^{N-1} \equiv 1 \mod N \Rightarrow \exists k \in \Z: a^{N-1} + kN=1 \Rightarrow \gcd(a,N)=1$. \\ +Aus der Kontraposition erhält man: Wenn $\gcd(a,N)\neq 1$, so wird der Fermat-Test sicher nicht bestanden. +\end{bem} + +\begin{bem}[Bemerkung zu $2.4$] + ``maximaler'' Wert von $\gcd(p-1,N-1)=p-1$. +\end{bem} + +\begin{proof}[Zu $2.4$] + \begin{subequations} + \begin{align} + \forall p \mid N, p \in \P: p-1 \mid N-1 \rightarrow \gcd(p-1,N-1)=p-1 \\ +\implies \prod \limits_{p \mid N} (p-1) \stackrel{\textsl{Quadratfreiheit}} = \varphi(N) + \end{align} + \end{subequations} +\end{proof} + +\begin{proof}[Beweis zu Satz $2.5$] + Sei $N$ eine Carmichael-Zahl, d.h. es gilt $N>1$ und $N$ ist zusammengesetzt. \\ + \begin{equation} + \gcd(N-1,N)=1 \stackrel{\textsl{in Test einsetzten}} \Rightarrow (N-1)^{(N-1)} \equiv (-1)^{(N-1)} \equiv 1 \mod N + \end{equation} +daher ist $N$ ungerade. \\ +Angenommen: $\exists p,q \in \P \land oBdA \, p < q: N=pq$. Dann folgt +\begin{subequations} + \begin{align} + q-1 \mid q-1 \label{diff1} \\ +p-1 \mid N-1=pq-1=p(p-1)+(p-1) \label{diff2} \\ +\Rightarrow q-1 \mid p-1 \label{differenz} + q < p \\ +\textsl{WS!} + \end{align} +\end{subequations} +Die Aussage in \eqref{differenz} ergibt sich aus der Tatsache, dass $(q-1)$ auch die Differenz aus \eqref{diff1} und \eqref{diff2} teilt, woraus sich unmittelbar \eqref{differenz} ergibt. +\end{proof} + +\begin{proof}[Beweis zu Satz $2.9$] + Sei $U:=\lbrace \bar{a} \in \Z_{N}^{*} \mid \bar{a}^{\left( \frac{N-1}{2} \right)} \equiv \left( \frac{a}{N} \right) \mod N \rbrace$. \\ +Man muss wieder nur die Abgeschlossenheit zeigen, daher: +\begin{subequations} + \begin{align} + \bar{a}_{1}, \bar{a}_{2} \in U: \bar{a}_{1}^{\left( \frac{N-1}{2} \right)} \equiv \left( \frac{\bar{a}_{1}}{N} \right) \mod N \land \bar{a}_{2}^{\left( \frac{N-1}{2} \right)} \equiv \left( \frac{\bar{a}_{2}}{N} \right) \mod N \\ +\Rightarrow \left( \bar{a}_{1} \bar{a}_{2} \right)^{\left( \frac{N-1}{2} \right)} = \left( \bar{a}_{1} \right)^{\left( \frac{N-1}{2} \right) } \cdot \left( \bar{a}_{2} \right)^{\left( \frac{N-1}{2} \right) } \equiv \\ +\equiv \left( \frac{\bar{a}_{1}}{N} \right) \cdot \left( \frac{\bar{a}_{2}}{2} \right) \stackrel{\textsl{starke Mult. i. Zähler}} = \left( \frac{\bar{a}_{1} \bar{a}_{2}}{N} \right) \mod N \\ +\Rightarrow \bar{a}_{1} \cdot \bar{a}_{2} = \bar{a_{1}a_{2}} \in U + \end{align} +\end{subequations} +Bemerkung: es gibt Zahlen mit $\vert U \vert = \frac{1}{2} \vert \Z_{N}^{*} \vert$. \\ +Wird der Test für $a_{1},a_{2}$ bestanden, wird der Test daher automatisch auch für $a_{1}a_{2}$ bestanden, d.h. ein Test mit $a_{1}a_{2}$ ist dann nicht sinnvoll. +\end{proof} + +\begin{bem} + Aus + \begin{equation} + a^{\left( \frac{N-1}{2} \right)} \equiv \underbrace{\left( \frac{a}{N} \right)}_{=\pm 1} \mod N + \end{equation} +erhält man durch quadrieren +\begin{equation} + a^{N-1} \equiv 1 \mod N, +\end{equation} +d.h. der Solovay-Strassen-Test ist eine Verschärfung des Fermat-Tests. +\end{bem} + +\begin{proof}[Beweis zu Miller-Rabin-Test] + Ist $N \in \P$, so gilt: + \begin{equation} + 0 < a < N \Rightarrow a^{N-1} \equiv 1 \mod N + \end{equation} +Für ein ungerade $N \in \N$ erhält man: gilt $a^{\frac{N-1}{2}} \nequiv \pm 1 \mod N$, so ist $N$ sicher zusammengesetzt. Erhält man $-1$, so wird der Miller-Rabin-Test bestanden. Erhält man $1$, zieht man solange die Wurzel, wie der Exponenent gerade ist. Daraus erhält man +\begin{enumerate} +\item $a^{s} = a^{\frac{N-1}{2^{t}}} \equiv 1 \mod N$? +\item if nein: kommt in der Folge + \begin{equation} + a^{s},(a^{s})^{2},\ldots, (a^{s})^{2^{(t-1)}} \mod N + \end{equation} +(die obige Folge ergibt sich durch (t-1)-faches Quadrieren). Kommt $-1$ nicht vor, so ist $N$ sicher zusammengesetzt. Kommt $-1$ vor, so wird der Test bestanden. +Die Grundlage für dieses Test ist: sei $p \in \P$: +\begin{subequations} + \begin{align} + x^{2} \equiv 1 \mod p \\ +\Rightarrow p \mid (x+1)(x-1) \\ +\Rightarrow p \mid (x+1) \vee p \mid (x-1) \\ +\Rightarrow x \equiv \pm 1 \mod p + \end{align} +\end{subequations} +\end{enumerate} +\end{proof} + +\begin{bem} + \begin{equation} + \sum_{n=1}^{\infty} \frac{1}{\ln(2^{2^{n}}+1)} \approx \frac{1}{\ln(2)} \cdot \underbrace{\sum_{n=1}^{\infty} \frac{1}{2^{n}}}_{=1} \approx \frac{1}{\ln(2)} \approx 1.44 + \end{equation} +``daher sollte es nur endlich viele Fermat-Primzahlen geben.'' +\begin{equation} + \sum \limits_{p \in \P} \frac{1}{\ln(2^{p}-1)} \approx \frac{1}{\ln(2)} \cdot \underbrace{\sum \limits_{p \in \P} \frac{1}{p}}_{\textsl{divergent nach Euler}} +\end{equation} +``es sollte $\infty$-viele Mersenne-Primzahlen geben'' +\end{bem} + +\begin{proof}[Beweis zu Satz $2.15$, Seite $23$] + $F_{n}=2^{2^{n}}+1$ + \begin{subequations} + \begin{align} + \Rightarrow F_{n}-1=2^{2^{n}} \cdot 1 \Rightarrow s=1,t=2^{n} \\ +\Rightarrow 2^{2^{n}} \equiv -1 \mod F_{n} \\ +\Rightarrow r=n F \cdot R = N-1\\ +\Rightarrow F^{2} \geq N \\ +\Rightarrow F \geq \sqrt{N} \geq q \\ +\end{align} +\end{subequations} +WS zu $F \mid q-1$, also $F < q$. +\end{proof} + +\begin{proof}[Beweis zu Satz $2.25$, Seite $25$] + Angenommen, die Voraussetzungen sind für $a \in \Z$ erfüllt, so gilt + \begin{equation} + N \mid a^{\frac{N-1}{2}} +1 \Rightarrow \gcd(a^{\frac{N-1}{2}}-1,N)=1 + \end{equation} +(denn sonst $p \mid a^{\frac{N-1}{2}}-1 \land p \mid N \Rightarrow p \mid \left(a^{\frac{N-1}{2}}+1 \right) - \left( a^{\frac{N-1}{2}} -1 \right)=2 \Rightarrow p=2$, WS zu $N$ ist ungerade). \\ +Unter Berufung auf $2.23$ (beachte dass $F>R$ wegen $2^{m} > h$ und dass $p_{1}=2$ der einzige Primfaktor von $F=2^{m}$ ist), folgt dann die Behauptung. +\end{proof} + +\begin{proof}[Beweis zu Satz $2.26$, Seite $25$] + Wegen $2.25$ (mit $k=1$ und $m=2^{n}$) ist die angegebene Bedingung für die Primalität von $F_{n}$ hinreichend. \\ +Ist umgekehrt $F_{n} \in \P$ und $n>0$ (insbesondere ist $F_{n}$ eine ungerade Primzahl), so gilt: +\begin{subequations} + \begin{align} + 3^{\frac{F_{n}-1}{2}} \stackrel{\textsl{Euler-Krit.}} \equiv \left( \frac{3}{F_{n}} \right) \stackrel{F_{n} \equiv 1 \mod 4 \textsl{ für } n>0} = \left( \frac{F_{n}}{3} \right)=\\ +=\left( \frac{2^{2^{n}}+1}{3} \right) \stackrel{2 \equiv -1 \mod 3} \equiv \left( \frac{(-1)^{2^{n}}+1}{3} \right) \stackrel{2^{n} \textsl{ gerade}} = \left( \frac{1+1}{3} \right)=\\ += \left( \frac{2}{3} \right) \stackrel{\textsl{2. Erg.satz}} = -1 + \end{align} +\end{subequations} +\end{proof} + +\begin{bem}[Bemerkung zu $2.29$] + $V_{2n}=V_{n}^{2}-2Q^{n}$ if $Q=1$, dann erhält man: $V_{2n}=V_{n}^{2}-2$ +\end{bem} + +\begin{bem}[Beispiel] + $M_{5}=2^{5}-1=31$ + \begin{subequations} + \begin{align} + s_{1}=4 \\ +s_{2}=16-2=14\\ +s_{3}=194 \equiv 8 \mod 31 \\ +s_{4}=64-2=62 \equiv 0 \mod 31 \Rightarrow s_{p-1}=s_{4} \equiv 0 \mod 31 + \end{align} + \end{subequations} +Daher gilt $M_{5} \in \P$ nach dem Lucas-Lehmer-Test. +\end{bem} + +\begin{proof}[Beweis zu Satz $3.1$, Seite $27$] + Zunächst gilt $p \nmid a \land p \nmid b$ (denn teilt $p$ eine der Zahlen $a$ oder $b$, dann wegen $p \mid a^{n}+b^{n}$ auch die andere, also $\gcd(a,b)=1$ WS, denn $1$ hat keine Primteiler).\\ +Es $\exists b^{\prime} \in \Z: b \cdot b^{\prime} \equiv 1 \mod p$. Setzt man nun $c:=ab^{\prime}$, sog gilt: +\begin{subequations} + \begin{align} + a^{n} \pm b^{n} \equiv 0 \mod p \\ +\Rightarrow a^{n} \equiv \mp b^{n} \mod p \quad / \cdot (b^{\prime})^{n} \\ +\Rightarrow \underbrace{a^{n}(b^{\prime})^{n}}_{=c^{n}} \equiv \mp \underbrace{b^{n}\cdot (b^{\prime})^{n}}_{\equiv 1 \mod p} \mod p\\ +\Rightarrow c^{n} \equiv \mp 1 \mod p + \end{align} +\end{subequations} +Wir betrachten zunächst +\begin{enumerate} +\item[1. Fall] $c^{n} \equiv +1 \mod p$: es gilt dann $ord_{p}(c)=n$: wäre nämlich $d:=ord_{p}(c) 0: M(n)=O(n^{\frac{1}{2}+\epsilon}) \right] \Leftrightarrow \text{Riemann'sche Vermutung} +\end{equation} +\end{bem} + +\begin{bem} + Aus $\Phi_{n}(x)=\prod \limits_{d \mid n} (x^{d}-1)^{\mu(\frac{n}{d})}$ erhält man beispielsweise + \begin{subequations} + \begin{align} + \Phi_{6}(x)=(x^{1}-1)^{\mu(6)}(x^{6}-1)^{\mu(1)}(x^{2}-1)^{\mu(3)}(x^{3}-1)^{\mu(2)}=\\ +=\frac{(x-1)(x^{6}-1)}{(x^{2}-1)(x^{3}-1)}=\frac{x^{3}+1}{x+1}=x^{2}-x+1 + \end{align} + \end{subequations} +\end{bem} + +\begin{bem}[Beispiel zu $3.5$] + \begin{subequations} + \begin{align} + a^{6}-b^{6}=\left( b^{\varphi(1)}\Phi_{1}(\frac{a}{b})\right) \left( b^{\varphi(2)}\Phi_{2}(\frac{a}{b}) \right) \left( b^{\varphi(3)}\Phi_{3}(\frac{a}{b}) \right) \left( b^{\varphi(6)}\Phi_{6}(\frac{a}{b}) \right)=\\ +=b(\frac{a}{b}-1)b(\frac{a}{b}+1)b^{2}(\frac{a^{2}}{b^{2}}+\frac{a}{b}+1)(b^{2}(\frac{a^{2}}{b^{2}}-\frac{a}{b}+1))=\\ +=(a-b)(a+b)(a^{2}+ab+b^{2})(a^{2}-ab+b^{2}) + \end{align} + \end{subequations} +\end{bem} + +\begin{proof}[Beweis zu Satz $3.7$, Seite $28$] + Zunächst genügt es, die Behauptung für alle Primteiler $q$ von $2^{p}-1$ zu zeigen, denn + \begin{equation} + \begin{cases} + t_{1} \equiv 1 \mod 2p \\ t_{2} \equiv 1 \mod 2p + \end{cases} + \end{equation} +und +\begin{equation} + \begin{cases} + t_{1} \equiv \pm 1 \mod 8 \\ t_{2} \equiv \pm 1 \mod 8 + \end{cases} +\end{equation} +\begin{equation} + \implies t_{1}t_{2} \equiv 1 \mod 2p \land t_{1}t_{2}\equiv \pm 1 \mod 8, +\end{equation} +d.h. gilt die Behauptung für Primteiler von $2^{p}-1$, dann auch für jeden anderen Teiler (der ja ein Produkt von Primteilern ist). \\ +Nach dem Satz von Legendre ($3.1$) folgt zunächst, dass tatsächlich $q\equiv 1 \mod 2p$ ist, da ja für Zahlen der Form $2^{p}-1 \land p \in \P$ jeder Primteiler primitiv ist. \\ +Nun gilt aber weiter: +\begin{subequations} + \begin{align} + q \mid 2^{p}-1 \Leftrightarrow 2^{p} \equiv 1 \mod q \\ +\stackrel{\textsl{Mult. mit } 2} \Leftrightarrow 2^{p+1} \equiv 2 \mod q \\ +\stackrel{p+1 \textsl{ gerade}} \Leftrightarrow 2^{\frac{p+1}{2}} \equiv 2 \mod q \\ +\Rightarrow \left( \frac{2}{q} \right) = 1 \\ +\stackrel{\textsl{2. Erg.satz}} \Leftrightarrow q \equiv \pm 1 \mod 8 + \end{align} +\end{subequations} +Es liegen nun 2 Fälle vor: +\begin{enumerate} +\item +\begin{equation} +q=2kp+1 \equiv 1 \mod 8 \Leftrightarrow 2kp \equiv 0 \mod 8 \Leftrightarrow kp \equiv 0 \mod 4 \Leftrightarrow k \equiv 0 \mod 4 +\end{equation} +\item + \begin{subequations} +\begin{align} + q=2kp+1 \equiv -1 \mod 8 \Leftrightarrow 2kp \equiv -2 \mod 8 \Leftrightarrow kp \equiv -1 \mod 4 \Leftrightarrow \\ +\stackrel{\textsl{Quadrat ung. Zahl ist } \equiv -1 \mod 4 } \Leftrightarrow kp^{2} \equiv -p \mod 4 \Rightarrow k \equiv -p \mod 4 +\end{align} + \end{subequations} +\end{enumerate} +\end{proof} + +% Vorlesung 20.6.2012 +\begin{bem}[Beispiel zu $3.7$] + $M_{67}=2^{67}-1, t=1+k\cdot 134 \Rightarrow k \equiv 0 \mod 4 \vee k \equiv 1 \mod 4$ +\end{bem} + +\begin{proof}[Beweis zu Satz $3.10$, Seite $28$] + Es genügt die Behauptung für Primteiler $q$ von $F_{n} (n\geq 2)$ zu zeigen, da das Produkt von Teilern dieser Form wieder diese Form hat. \\ + \begin{subequations} + \begin{align} + F_{n}=2^{2^{n}}+1 \equiv 0 \mod q \\ +\Rightarrow 2^{2^{n}} \equiv -1 \mod q \land 2^{2^{n+1}} \equiv 1 \mod q \textsl{ (Quadrieren) } \\ +\Rightarrow ord_{q}(2) \mid 2^{n+1} + \end{align} + \end{subequations} +Da aber auch $2^{2^{n}} \equiv -1 \mod -1 \mod q$ gilt, folgt daher $ord_{q}(2)=2^{n+1}$. \\ +Wegen $2^{q-1} \equiv 1 \mod q$ (kl. Fermat) folgt daraus zunächst einmal, dass $2^{n+1} \mid q-1$ (weil $ord_{q}(2) \mid q-1)$. \\ +Aus $n\geq 2$ folgt nun weiter +\begin{subequations} +\begin{align} + 8 \mid q-1 \Rightarrow q \equiv 1 \mid 8\\ +\Rightarrow 2^{\frac{q-1}{2}} \stackrel{\textsl{Euler-Krit.}} \equiv \left( \frac{2}{q} \right) \equiv 1 \mod q \textsl{ nach 2. Erg.satz} +\end{align} +\end{subequations} +und daher +\begin{subequations} + \begin{align} + ord_{q}(2) = 2^{n+1} \mid \frac{q-1}{2} \\ +\Rightarrow 2^{n+2} \mid q-1 \\ +\Rightarrow q \equiv 1 \mod 2^{n+2} + \end{align} +\end{subequations} +\end{proof} + +\begin{bem}[Beispiel zu Satz $3.10$] +Es gilt $5 \cdot 2^{1947}+1 \mid 2^{2^{1945}}+1, k=5$ aus Satz $3.10$. +\end{bem} + +\begin{proof}[Beweis zu Satz $3.14$, Seite $30$] + Zunächst gilt nach der Formel ``günstige/mögliche'': + \begin{subequations} + \begin{align} + P_{k,m}=\left( \frac{m-1}{m} \right) \left( \frac{m-2}{m} \right) \cdot \ldots \cdot \left( \frac{m-k+1}{m} \right)=\\ +=(1-\frac{1}{m})(1-\frac{2}{m})\ldots(1-\frac{k-1}{m}) + \end{align} + \end{subequations} +Unter der Voraussetzung, dass $k<