dlog auf ell. Kurven < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:45 Di 27.03.2012 | | Autor: | Teufel |
Hi!
Ich schreibe gerade meine bachelorarbeit über das Thema "Die Berechnung des diskreten Logarithmus auf elliptischen Kurven in subexponentieller Zeit". Als Grundlage habe ich folgendes Paper von Claus Diem: ![[]](/images/popup.gif) Link.
In diesem Thread will ich meine Fragen sammeln, weil das Thema schon ziemlich spezifisch ist.
Ich fange mal mit meiner ersten Frage an:
Auf Seite 3 steht das zentrale Theorem der Arbeit. Direkt danach wird behauptet, dass man mit diesem Theorem Aussage 1 auf Seite 2 einfach zeigen kann. Ich sehe nur nicht, wie das so einfach gehen soll.
Es gelte also dass man den diskreten Logarithmus auf einer elliptischen Kurve über [mm] \mathbb{F}_{q^n} [/mm] in erwarteter Zeit [mm] e^{\mathcal{O}(\max (\log q, n^2))} [/mm] lösen kann. Nun habe ich Folgen [mm] (q_i) [/mm] und [mm] (n_i) [/mm] wobei die [mm] q_i [/mm] Primzahlpotenzen und [mm] n_i [/mm] natürliche Zahlen sind und [mm] n_i \rightarrow \infty [/mm] und [mm] \frac{n_i}{\log q_i} \rightarrow [/mm] 0 gilt für i [mm] \to \infty.
[/mm]
Zu zeigen: Das dlog-Problem lässt sich in erwarteter Zeit [mm] (q_i^{n_i})^{o(1)} [/mm] lösen.
Dann setze ich mal [mm] a_i:=\frac{n_i}{\log q_i}. [/mm] Es gilt, dass [mm] a_i [/mm] eine Nullfolge ist, also in $o(1)$ liegt. Dann ist also [mm] $n_i [/mm] = [mm] \log q_i [/mm] * [mm] a_i \in \log q_i \cdot [/mm] o(1)$. Setzt man das ins Theorem ein, erhält man, dass das dlog-Problem in erwarteter Zeit [mm] e^{\mathcal{O}(\max (\log q_i, n_i*a_i*\log q_i))} [/mm] lösbar ist. Wenn man nun davon ausgehen könnte, dass [mm] $n_i*a_i*\log q_i>\log q_i$ [/mm] gilt, dann hätte man [mm] e^{\mathcal{O}(n_i*a_i*\log q_i)} [/mm] und wenn man dann das [mm] \mathcal{O} [/mm] noch ignorieren dürfte hätte man das gewünschte Ergebnis [mm] (q_i^{n_i})^{o(1)}. [/mm] Aber ich weiß nicht, wie ich diese kleinen Zwischenschritte und Annahmen vernünftig zeigen kann.
Kann mir da bitte jemand helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:25 Mi 28.03.2012 | | Autor: | felixf |
Moin Teufel!
> Ich schreibe gerade meine bachelorarbeit über das Thema
> "Die Berechnung des diskreten Logarithmus auf elliptischen
> Kurven in subexponentieller Zeit". Als Grundlage habe ich
> folgendes Paper von Claus Diem:
> Link.
>
> In diesem Thread will ich meine Fragen sammeln, weil das
> Thema schon ziemlich spezifisch ist.
>
> Ich fange mal mit meiner ersten Frage an:
> Auf Seite 3 steht das zentrale Theorem der Arbeit. Direkt
> danach wird behauptet, dass man mit diesem Theorem Aussage
> 1 auf Seite 2 einfach zeigen kann. Ich sehe nur nicht, wie
> das so einfach gehen soll.
>
> Es gelte also dass man den diskreten Logarithmus auf einer
> elliptischen Kurve über [mm]\mathbb{F}_{q^n}[/mm] in erwarteter
> Zeit [mm]e^{\mathcal{O}(\max (\log q, n^2))}[/mm] lösen kann. Nun
> habe ich Folgen [mm](q_i)[/mm] und [mm](n_i)[/mm] wobei die [mm]q_i[/mm]
> Primzahlpotenzen und [mm]n_i[/mm] natürliche Zahlen sind und [mm]n_i \rightarrow \infty[/mm]
> und [mm]\frac{n_i}{\log q_i} \rightarrow[/mm] 0 gilt für i [mm]\to \infty.[/mm]
>
> Zu zeigen: Das dlog-Problem lässt sich in erwarteter Zeit
> [mm](q_i^{n_i})^{o(1)}[/mm] lösen.
>
> Dann setze ich mal [mm]a_i:=\frac{n_i}{\log q_i}.[/mm] Es gilt, dass
> [mm]a_i[/mm] eine Nullfolge ist, also in [mm]o(1)[/mm] liegt. Dann ist also
> [mm]n_i = \log q_i * a_i \in \log q_i \cdot o(1)[/mm]. Setzt man das
> ins Theorem ein, erhält man, dass das dlog-Problem in
> erwarteter Zeit [mm]e^{\mathcal{O}(\max (\log q_i, n_i*a_i*\log q_i))}[/mm]
> lösbar ist. Wenn man nun davon ausgehen könnte, dass
> [mm]n_i*a_i*\log q_i>\log q_i[/mm] gilt, dann hätte man
> [mm]e^{\mathcal{O}(n_i*a_i*\log q_i)}[/mm] und wenn man dann das
> [mm]\mathcal{O}[/mm] noch ignorieren dürfte hätte man das
> gewünschte Ergebnis [mm](q_i^{n_i})^{o(1)}.[/mm] Aber ich weiß
> nicht, wie ich diese kleinen Zwischenschritte und Annahmen
> vernünftig zeigen kann.
Du hattest ja bereits [mm] $\max\{ \log q_i, n_i^2 \} [/mm] = [mm] \max\{ \log q_i, n_i \log q_i \cdot a_i \}$.
[/mm]
Jetzt ist [mm] $\log q_i [/mm] = [mm] n_i \log q_i \cdot b_i$ [/mm] mit [mm] $b_i [/mm] := [mm] \frac{1}{n_i}$. [/mm] Damit hast du [mm] $\max\{ \log q_i, n_i^2 \} [/mm] = [mm] n_i \log q_i \cdot c_i$ [/mm] mit [mm] $c_i [/mm] := [mm] \max\{ a_i, b_i \}$. [/mm] Wegen [mm] $a_i \to [/mm] 0$ und [mm] $b_i \to [/mm] 0$ gilt auch [mm] $c_i \to [/mm] 0$.
Ist schliesslich die Laufzeit [mm] $\exp(f(i))$, [/mm] so gilt $f(i) = [mm] O(\max\{ \log q_i, n_i^2 \})$ [/mm] und somit $f(i) [mm] \le [/mm] C [mm] \cdot \max\{ \log q_i, n_i^2 \}$ [/mm] fuer ein gross genuges $C$. Nun ist $f(i) [mm] \le [/mm] C [mm] \cdot n_i \log q_i \cdot c_i$, [/mm] also [mm] $\exp(f(i)) \le \exp(n_i \log q_i \cdot [/mm] (C [mm] \cdot c_i)) [/mm] = [mm] (q_i^{n_i})^{C \cdot c_i}$. [/mm] Wegen $C [mm] \cdot c_i \to [/mm] 0$ fuer $i [mm] \to \infty$ [/mm] hast du im Endeffekt also [mm] $(q_i^{n_i})^{o(1)}$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:37 Mi 28.03.2012 | | Autor: | Teufel |
Vielen Dank!
Das war ja wirklich gar nicht so schwierig. Ich mach dann erst einmal weiter und melde mich dann wieder, wenn ich hänge.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:10 Mi 25.04.2012 | | Autor: | Teufel |
Hallo!
Hat jemand Quellen zum Beweis zu einem Satz, dass die Gruppe [mm] $E[\mathbb{F}_{q^n}]$ ($\mathbb{F}_{q^n}$-rationalen [/mm] Punkte einer elliptischen Kurve) endlich erzeugt ist? Es gilt wohl, dass man immer höchstens 2 Elemente aus der Gruppe für ein Erzeugendensystem braucht, aber ich weiß nicht, wie der Satz heißt, der das besagt (oder ob er überhaupt einen speziellen Namen hat). Ich kennen nur das Mordell-Weil-Theorem, das besagt, dass [mm] E[\IQ] [/mm] endlich erzeugt ist, aber etwas anderes fällt mir nicht zu der Problematik ein.
Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:16 Do 26.04.2012 | | Autor: | felixf |
Moin!
> Hat jemand Quellen zum Beweis zu einem Satz, dass die
> Gruppe [mm]E[\mathbb{F}_{q^n}][/mm] ([mm]\mathbb{F}_{q^n}[/mm]-rationalen
> Punkte einer elliptischen Kurve) endlich erzeugt ist?
Die Gruppe ist offenbar endlich (es gibt hoechstens [mm] $(q^n)^2 [/mm] + 1$ viele Elemente in [mm] $E(\mathbb{F}_{q^n})$) [/mm] und somit insbesondere endlich erzeugt.
> Es gilt wohl, dass man immer höchstens 2 Elemente aus der
> Gruppe für ein Erzeugendensystem braucht, aber ich weiß
> nicht, wie der Satz heißt, der das besagt (oder ob er
> überhaupt einen speziellen Namen hat).
Du brauchst, dass fuer jedes $n [mm] \in \IN$ [/mm] die Gruppe $E[n] = [mm] \{ P \in E(\overline{k}) \mid n P = \infty \}$ [/mm] isomorph zu [mm] $\IZ/n\IZ \times \IZ/n\IZ$ [/mm] (oder einer Untergruppe dazu: das kann aber nur passieren falls $n$ durch die Charakteristik von $k$ teilbar ist) ist.
Daraus folgt, dass jede endliche Untergruppe von $E(k)$ bzw. [mm] $E(\overline{k})$ [/mm] von der Form [mm] $\IZ/n\IZ \times \IZ/m\IZ$ [/mm] sein muss. Soweit ich weiss hat dieses Resultat keinen speziellen Namen.
> Ich kennen nur das
> Mordell-Weil-Theorem, das besagt, dass [mm]E[\IQ][/mm] endlich
> erzeugt ist, aber etwas anderes fällt mir nicht zu der
> Problematik ein.
Der Satz von Mordell-Weil ist wesentlich viel komplizierter.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:28 Do 26.04.2012 | | Autor: | Teufel |
Hi!
Ok, vielen Dank! Das mit dem [mm] $E[n]\cong Z_n \times Z_n$ [/mm] habe ich auch schon einmal gesehen. Kann man die nächste Aussage dann so folgern:
Sei $N:=|E[K]|$. Dann gilt ja [mm] $E[K]=E[N]\cong Z_N \times Z_N$ [/mm] wegen E[K] [mm] \subseteq [/mm] E[N] (alle Elemente mal Gruppenordnung ergeben [mm] \infty) [/mm] und E[N] [mm] \subseteq [/mm] E[K] (klar).
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:53 Do 26.04.2012 | | Autor: | felixf |
Moin!
> Ok, vielen Dank! Das mit dem [mm]E[n]\cong Z_n \times Z_n[/mm] habe
> ich auch schon einmal gesehen. Kann man die nächste
> Aussage dann so folgern:
>
> Sei [mm]N:=|E[K]|[/mm]. Dann gilt ja [mm]E[K]=E[N]\cong Z_N \times Z_N[/mm]
Nein, das stimmt nicht.
$E[K]$ ist eine Untergruppe von $E[N]$, jedoch im Allgemeinen nicht gleich!
> wegen E[K] [mm]\subseteq[/mm] E[N] (alle Elemente mal Gruppenordnung
> ergeben [mm]\infty)[/mm] und E[N] [mm]\subseteq[/mm] E[K] (klar).
Der "klar"-Teil ist falsch. Die Elemente von $E[N]$ sind i.A. Elemente aus [mm] $E[\overline{K}]$, [/mm] und liegen eher selten in $E[K]$ (ausser fuer bestimmte $N$ halt).
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:49 Do 26.04.2012 | | Autor: | Teufel |
Oh, ok, danke!
Dann sollte ich vielleicht einfach so argumentieren:
[mm] $E[N]\cong Z_N \times Z_N$ [/mm] und E[K] ist eine Untergruppe von E[N]. Und die Untergruppen von [mm] $Z_N \times Z_N$ [/mm] sind wohl dann genau Gruppen der Form [mm] $Z_n \times Z_m$, [/mm] oder? Wobei [mm] Z_n, Z_m [/mm] Untergruppe von [mm] Z_N [/mm] sind.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:00 Do 26.04.2012 | | Autor: | felixf |
Moin!
> Oh, ok, danke!
>
> Dann sollte ich vielleicht einfach so argumentieren:
>
> [mm]E[N]\cong Z_N \times Z_N[/mm] und E[K] ist eine Untergruppe von
> E[N]. Und die Untergruppen von [mm]Z_N \times Z_N[/mm] sind wohl
> dann genau Gruppen der Form [mm]Z_n \times Z_m[/mm], oder?
Sie sind isomorph dazu, ja. Das ist allerdings nicht ganz trivial. Kennst du den Elementarteilersatz?
> Wobei
> [mm]Z_n, Z_m[/mm] Untergruppe von [mm]Z_N[/mm] sind.
Nein. Das ist falsch. Die von $(1, 1)$ erzeugte Untergruppe von [mm] $\IZ_N \times \IZ_N$ [/mm] ist definitiv nicht von dieser Form (ausser falls $|N| [mm] \le [/mm] 1$ ist).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:04 Do 26.04.2012 | | Autor: | Teufel |
Hmmmm, ok. Nein, den Satz kenne ich nicht. Aber das würde auch sicher etwas zu weit gehen den noch mit aufzunehmen...
Aber ich werde den Fakt mit aufnehmen, dass E[N] isomorph zu [mm] Z_N \times Z_N [/mm] ist und dass die Untergruppen davon isomorph zu [mm] Z_n \times Z_m [/mm] sind.
Vielen Dank (mal wieder)!
|
|
|
|
