Kryptographie - Algebraischer Hintergrund

Prof . Dr. F.-O. Schreyer

Übungsblatt 3: Elliptische Kurven und Faktorisierung

Abgabetermin 21.5.2002

Voraussetzungen: Vorlesungskapitel Faktorisierung, Elliptische Kurven.

1. Für q eine Primzahl. Schreiben Sie eine Maple-Prozedur, die die Punke einer

   elliptischen Kurve

   E_{a, b}$$\left(\vphantom{ \mathbb{F}_{q}}\right.$$$$\mathbb {F}$$_q$$\left.\vphantom{ \mathbb{F}_{q}}\right)$$ = $$\left\{\vphantom{ \left( x,y\right) \in\mathbb{F}_{q}^{2}\mid y^{2}=x^{3}+ax+b}\right.$$$$\left(\vphantom{ x,y}\right.$$x, y$$\left.\vphantom{ x,y}\right)$$ $$\in$$ $$\mathbb {F}$$_q² | y² = x³ + ax + b$$\left.\vphantom{ \left( x,y\right) \in\mathbb{F}_{q}^{2}\mid y^{2}=x^{3}+ax+b}\right\}$$ $$\cup$$ $$\left\{\vphantom{ O}\right.$$O$$\left.\vphantom{ O}\right\}$$
   a, b $\in$ $\mathbb {F}$_q bestimmt.

2. Für q eine Primzahl. Schreiben Sie eine Maple-Prozedur, die die Anzahl $\left\vert\vphantom{ E_{a,b}\left( \mathbb{F}_{q}\right) }\right.$E_{a, b}$\left(\vphantom{ \mathbb{F}_{q}}\right.$$\mathbb {F}$_q$\left.\vphantom{ \mathbb{F}_{q}}\right)$$\left.\vphantom{ E_{a,b}\left( \mathbb{F}_{q}\right) }\right\vert$ der Punke der elliptischen Kurve E_{a, b}$\left(\vphantom{ \mathbb{F}_{q}}\right.$$\mathbb {F}$_q$\left.\vphantom{ \mathbb{F}_{q}}\right)$ bestimmt (Vergessen Sie den Punkt im Unendlichen nicht).

3. Bestimmen Sie für alle Primzahlen 5 $\leq$ p $\leq$ 29 die Anzahl der Punkte von E$\left(\vphantom{ \mathbb{F}_{p}}\right.$$\mathbb {F}$_p$\left.\vphantom{ \mathbb{F}_{p}}\right)$ : y² = x³ + 1. Wann ist $\left\vert\vphantom{ E\left( \mathbb{F}_{p}\right) }\right.$E$\left(\vphantom{ \mathbb{F}_{p}}\right.$$\mathbb {F}$_p$\left.\vphantom{ \mathbb{F}_{p}}\right)$$\left.\vphantom{ E\left( \mathbb{F}_{p}\right) }\right\vert$ = p + 1 ?

4. Für q eine Primzahl. Schreiben Sie eine Maple-Prozedur, die $\left\vert\vphantom{ E_{a,b}\left( \mathbb{F}_{q}\right) }\right.$E_{a, b}$\left(\vphantom{ \mathbb{F}_{q}}\right.$$\mathbb {F}$_q$\left.\vphantom{ \mathbb{F}_{q}}\right)$$\left.\vphantom{ E_{a,b}\left( \mathbb{F}_{q}\right) }\right\vert$ für alle a, b $\in$ $\mathbb {F}$_q bestimmt und damit den Satz von Hasse verifiziert.

5. Schreiben Sie eine Maple-Prozedur, die P + Q für zwei Punkte P und Q auf einer elliptischen Kurve E_{a, b}$\left(\vphantom{ \mathbb{F}_{q}}\right.$$\mathbb {F}$_q$\left.\vphantom{ \mathbb{F}_{q}}\right)$ berechnet. Vergessen Sie den Fall P = Q und den Punkt O im Unendlichen nicht.

6. Sei t $\in$ $\mathbb {N}$ und P $\in$ E_{a, b}$\left(\vphantom{ \mathbb{F}_{q}}\right.$$\mathbb {F}$_q$\left.\vphantom{ \mathbb{F}_{q}}\right)$. Schreiben Sie ein Maple-Skript, das t ^. P berechnet.

7. Schreiben Sie ein Maple-Skript, das die elliptische-Kurven-Faktorisierung wie in der Vorlesung beschrieben durchführt.

8. Versuchen Sie die Zahlen aus dem Übungsblatt 2 mit Ihrem Skript zur elliptischen-Kurven-Faktorisierung zu faktorisieren.

Abgabe der Aufgaben bitte als Maple-file per email an boehm@math.uni-sb.de.