Solovay-Strassen-Algorithmus < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo Leute,
Ich würde gerne wissen, welche schnellen Möglichkeiten es gibt das Jacobi-Symbol "von Hand" zu berechnen?
Eine andere Frage wäre wie ich schnell die Modulo-Operation "per Hand" auf große Potenzen ganzer Zahlen anwenden kann?
Im Internet bin ich bisher auf den kleinen Satz von Fermat gestossen. Im Moment bin ich mir aber nicht sicher, ob er mich weiterbringt. Und das Jacobi-Symbol soll sich rekursiv berechnen lassen?
Mir würde auch schon ein Link zu den entsprechenden Verfahren reichen, die ich dann durcharbeiten könnte.
Vielen Dank für eure Mühe!
Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:39 Sa 17.09.2005 | | Autor: | Stefan |
Lieber Karl!
Wegen
[mm] $\left( \frac{p}{q} \right) [/mm] = [mm] \left( \frac{p \pmod{q}}{q} \right)$
[/mm]
kannst du ja immer $p <q$ erreichen.
Wegen
[mm] $\left( \frac{pp'}{q} \right) [/mm] = [mm] \left( \frac{p}{q} \right) \left( \frac{p'}{q} \right)$
[/mm]
kann man stets $p$ prim annehmen (sonst zerlegt man $p$ und das Jacobi-Symbol wie gerade).
Wegen
[mm] $\left( \frac{2}{q} \right) [/mm] = [mm] (-1)^{\frac{q^2-1}{8}}$
[/mm]
können wir oBdA $p [mm] \ne [/mm] 2$ annehmen.
Ist in diesem Fall ($p$ prim, $p<q$, [mm] $p\ne [/mm] 2$) der Ausdruck
[mm] $\left( \frac{p}{q} \right)$
[/mm]
immer noch schwer zu bestimmen, dann werden man das quadratische Reziprozitätsgesetz an:
[mm] $\left( \frac{p}{q} \right) [/mm] = [mm] (-1)^{\frac{(p-1)(q-1)}{4}} \cdot \left( \frac{q}{p} \right)$,
[/mm]
und fährt wie oben fort.
Kommst du damit klar? Willst du es mal an Beispielen selber üben und diese hier zur Kontrolle (oder bei Fragen) hier hereinstellen? 
Liebe Grüße
Stefan
|
|
|
| |
|
Hallo Stefan!
Ich kopiere den Algorithmus nochmal rein, bevor ich anfange:
[mm]\begin{array}{l}
\texttt{choose }a\in\{1,2,\dotsc,n-1\}\texttt{ at random};\\
\textbf{if }\gcd(a,n)\ne 1\textbf{ then}\\
\qquad\textbf{return }\texttt{`Composite'};\\
\textbf{else}\\
\qquad\textbf{if }\left(\frac{a}{n}\right)\not\equiv a^{\frac{n-1}{2}}\mod n\textbf{ then}\\
\qquad\qquad\textbf{return }\texttt{`Composite'};
\end{array}[/mm]
Ok, los gehts:
Beispiel 1:
Sei $n := 17$. Wähle zufällig $a := 13$. Dann gilt:
(1) [mm] $\mathrm{ggT}\left(13, 17\right) [/mm] = 1$, weil das beides Primzahlen sind.
(2) Berechne das Jacobi-Symbol:
[mm] $\left(\frac{13}{17}\right) \mathop [/mm] = [mm] ^{\text{Regel 4}} \left(-1\right)^{\frac{12*16}{4}}\left(\frac{17}{13}\right) [/mm] = [mm] \left(\frac{17}{13}\right) \mathop [/mm] = [mm] ^{\text{Regel 1}} \left(\frac{4}{13}\right) \mathop [/mm] = [mm] ^{\text{Regel 2}} \left(\frac{2}{13}\right)\left(\frac{2}{13}\right) \mathop =^{\text{Regel 3}} \left(\left(-1\right)^{\frac{13^2-1}{8}}\right)^2 [/mm] = [mm] \left(-1\right)^{\frac{168}{4}} [/mm] = [mm] \left(-1\right)^{42} [/mm] = 1$ und $1 [mm] \pmod{17} [/mm] = 1$
(3) Berechne:
[mm] $13^{\frac{16}{2}} \pmod{17} [/mm] = [mm] \left(13^2\right)^4 \pmod{17} [/mm] = [mm] \left(13^2 \pmod{17}\right)^4 \pmod{17} [/mm] = [mm] \left(16^2\right)^2 \pmod{17} \mathop [/mm] = ^{256 [mm] \pmod{17} [/mm] = 1} 1$
[mm] $\Rightarrow:$ [/mm] 17 ist vermutlich eine Primzahl.
Beispiel 2:
Sei jetzt $n := 9$. Wähle zufällig $a := 6$. Dann gilt:
(1) [mm] $\mathrm{ggT}\left(9, 6\right) [/mm] = [mm] \mathrm{ggT}\left(6,3\right) [/mm] = [mm] \mathrm{ggT}\left(3,0\right) [/mm] = 3 [mm] \ne [/mm] 1 [mm] \Rightarrow 9\text{ ist eine zusammengesetzte Zahl!}$.
[/mm]
Wähle zufällig $a := 5$. Dann gilt:
(1) [mm] $\mathrm{ggT}\left(9,5\right) [/mm] = [mm] \mathrm{ggT}\left(5,4\right) [/mm] = [mm] \mathrm{ggT}\left(4,1\right) [/mm] = 1$
(2) Berechne das Jacobi-Symbol:
[mm] $\left(\frac{5}{9}\right) [/mm] = [mm] \left(-1\right)^{\frac{4*8}{4}}\left(\frac{9}{5}\right) [/mm] = [mm] \left(\frac{4}{5}\right) [/mm] = [mm] \left(-1\right)^{\frac{3*4}{4}}\left(\frac{5}{4}\right) [/mm] = [mm] -\left(\frac{1}{4}\right) [/mm] = [mm] -\left(\frac{4}{1}\right) [/mm] = [mm] -\left(\frac{0}{1}\right) [/mm] = [mm] \red{-1}?$.
[/mm]
(3) Berechne:
[mm] $5^4 \pmod{9} [/mm] = [mm] 25^2 \pmod{9} [/mm] = [mm] 7^2 \pmod{9} [/mm] = 4 [mm] \ne \red{-1}$? [/mm] Also ist 9 mit Sicherheit keine Primzahl!
Stimmt das so?
Danke! 
Viele Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:56 Sa 17.09.2005 | | Autor: | Stefan |
Lieber Karl!
Du hast das alles meines Erachtens völlig richtig gemacht (allerdings bin ich auch kein Experte auf dem Gebiet).
Allerdings ist mir im Moment unklar, wie [mm] $\left( \frac{0}{1} \right)$ [/mm] definiert ist, d.h. ob dies gleich $0$ oder $1$ ist. Auch weiß ich nicht genau, ob [mm] $\left( \frac{a}{b} \right)$ [/mm] überhaupt definiert ist, wenn $b<3$ gilt oder wenn $b$ durch $2$ teilbar ist. Ich finde darüber unterschiedliche Informationen im Netz.
Daher lasse ich die Frage mal auf "teilweise beantwortet", damit dies geklärt werden kann.
Wie habt ihr das Jacobi-Symbol denn genau in der Vorlesung definiert?
Uih, es wäre mir lieb, wenn noch ein Experte antwortet, auch wenn er mich dann verbessert (das verkrafte ich, ich habe mich zuletzt im Sommersester 1996 (?) damit beschäftigt, als ich Zahlentheorie-Tutor war... ).
Liebe Grüße
Stefan
|
|
|
| |
|
Lieber Stefan!
Danke für die Hilfe!
> Wie habt ihr das Jacobi-Symbol denn genau in der Vorlesung
> definiert?
Offenbar ist dieses Jacobi-Symbol ja nur eine Erweiterung des Legendre-Symbols? Na ja, die Beweise dort waren mir alle zu kompliziert, aber ich stelle die dortigen Formeln mal zusammen:
[mm]\left(\frac{a}{p}\right) := \begin{cases}
+1&\texttt{falls }a\texttt{ Quadratzahl im }\mathbb{Z}_p^{\*}\texttt{ ist}\\
-1&\texttt{sonst}
\end{cases}[/mm]
[mm]\left(\frac{1}{p}\right)=1[/mm] sowie [mm]\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\cdot{}\left(\frac{b}{p}\right)[/mm]
[mm]\left(\frac{a}{n}\right)\in\{+1,-1\}[/mm]
[mm]\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)\cdot{}(-1)^{\frac{p+1}{2}\cdot{}\frac{q-1}{2}}[/mm]
Bei einer Formel steht im Exponenten ein Plus statt eines Minus aber ich habe inzwischen auch im Netz nachgeforscht, und denke, daß das dort ein Tippfehler ist. Die anderen Formeln sind doch so wie bei dir, denke ich.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:17 So 18.09.2005 | | Autor: | Stefan |
Lieber Karl!
Auf Grund deiner Ergänzungen kann ich jetzt noch einmal darauf eingehen. Also, bei euch ist ja [mm] $\left( \frac{a}{p} \right)$ [/mm] nur dann definiert, wenn $ggT(a,p)=1$ ist, und es gilt: [mm] $\left( \frac{1}{p} \right)=1$.
[/mm]
> [mm]\left(\frac{5}{9}\right) = \left(-1\right)^{\frac{4*8}{4}}\left(\frac{9}{5}\right) = \left(\frac{4}{5}\right) = \left(-1\right)^{\frac{3*4}{4}}\left(\frac{5}{4}\right) = -\left(\frac{1}{4}\right) = -\left(\frac{4}{1}\right) = -\left(\frac{0}{1}\right) = \red{-1}?[/mm].
Dann müsstest du es so modifizieren:
[mm]\left(\frac{5}{9}\right) = \left(-1\right)^{\frac{4*8}{4}}\left(\frac{9}{5}\right) = \left(\frac{4}{5}\right) = \left(-1\right)^{\frac{3*4}{4}}\left(\frac{5}{4}\right) = -\left(\frac{1}{4}\right) \red{=-1}[/mm].
Der Rest stimmt dann!
Liebe Grüße
Stefan
|
|
|
|
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]"){kind=small}
![[read]](/images/smileys/read.gif "[read]"){kind=small}
