Übung 10 Aufgabe P1 a

[itportal2]

Hallo zusammen,

kann mir jemand die Lösung von Übung 10 Aufgabe P1 a) (DSA Signatur) erklären? So weit ich sehe wird es überprüft, ob einer von den ungeraden Zahlen 3, 5, ... Primitivwurzel modulo p ist. Deswegen wird auch getestet, ob die Zahl hoch die möglichten Teiler von der Gruppenordnung (früher) eine eins ergibt. So bekommt man 5, weil das bei 5 nicht der Fall ist.

Mich stört folgendes. In meinen Notizen aus der Vorlesung steht, dass x zufällig gewählt wird und man soll nur überprüfen, ob das resultierende g nicht kongruent modulo p ist. Wenn das so ist, ist x zu akzeptieren. Wenn man dieses Schema folgt, komme ich auf 3, weil ja \(3^{6}\equiv8\pmod{p}\) ist. Sind jetzt meine Notizen unvollständig oder übersehe ich etwas?

[dees]

Also ich kann dir nicht genau sagen wie wir es in der Vorlesung definiert haben aber im Buch steht, dass x eine Primitivwurzel mod p sein muss und sich g wie folgt berechnet \(g = x^{(p-1)/q} \; mod \; p\) . Damit ist sichergestellt, dass g die Ordnung von q hat.

[olg]

Da scheint es eine Diskrepanz von Buch und VL/Fips zu geben:

Nach dem Buch läuft es wie itportal2 geschrieben hat: x muss eine Primitivwurzel sein, dann würde die Lösung aus Ex10 a) so stimmen [man wählt x=5, da x^(3*17) mod 102].

In der Vorlesung habe ich es mir wie folgt notiert (Die Mitschriften hier aus dem Forum sind analog dazu):

Wähle zufälliges \(x \in \{1,\ldots,p-1\}\) und prüfe ob \(x^(p-1)/q \not\equiv 1\).
Falls ja, setze g = x. g hat dann die Ordnung q in \((\mathbb{Z}/p\mathbb{Z})*\).
Ansonsten wähle neues x.

Im aktuellen Fips 186 v3 wird g als Generator der Untergruppe der Ordnung q mod p verlangt.

g: A generator of the subgroup of order q mod p, such that \(1 < g < p\)

Wenn ich das aus der Vorlesung mal nachrechne, und dabei die Anforderung in der Übung (möglichst kleines x und x ungerade) wähle, dann erhalte ich für x = 3:

\(g = 3^{(p-1) / q} = 3^6 \text{ mod } 103 \equiv 8\).

Da \(g \not\equiv 1 \text{ mod } 103\), folgt dass die Ordnung von g = q entspricht: Und tatsächlich:

Code: Alles auswählen

8^1 mod 103 -> 8
8^2 mod 103 -> 64
8^3 mod 103 -> 100
8^4 mod 103 -> 79
8^5 mod 103 -> 14
8^6 mod 103 -> 9
8^7 mod 103 -> 72
8^8 mod 103 -> 61
8^9 mod 103 -> 76
8^10 mod 103 -> 93
8^11 mod 103 -> 23
8^12 mod 103 -> 81
8^13 mod 103 -> 30
8^14 mod 103 -> 34
8^15 mod 103 -> 66
8^16 mod 103 -> 13
8^17 mod 103 -> 1

Vielleicht ist das ein Zufall und der Ansatz aus der Vorlesung ist nicht vollständig. Ich habe es bisher zumindest wie in der Lösung gemacht (x als Primitivwurzel, dann fällt die 3 natürlich weg).

[itportal2]

Ich habe auch die Vermuting, dass der Professor in der Vorlesung sagen wollte, dass x eine zufällige Primitivwurzel aus der Gruppe ist. Das Wort "Primitivwurzel" hat er ja scheinlich vergessen.

EDIT:
Wenn x Primitivwurzel modulo p ist, sollte \(x^{(p-1)/q}\not\equiv 1\pmod{p}\) immer erfüllt sein.

[olg]

Ich habe auch nochmal etwas nachgehakt (danke Felix!) und das 'korrekte' Vorgehen ist, x als Primitivwurzel zu wählen.

Mit zufälligen x funktioniert es in primen Untergruppen von p:

p-1 lässt sich als Primfaktoren \(q, r_i\) schreiben:
\(order(G) = p - 1 = q \cdot \underbrace{r_1 \cdot \ldots \cdot r_n}_{r}\)

Und es gilt:
\((p-1)/q = r\)

Wählt man ein zufälliges x und berechnet \(x^r\), dann gibt es zwei Fälle:
1) \(x^r\) ist Element einer anderen Untergruppe \(r_k\), daher gilt
\(x^r = (x^{r_k})^{\prod_{i \neq k}^{n} r_i} = 1^{\prod_{i \neq k}^{n} r_i} \equiv 1 \text{ (mod p })\)
Dann wählt man also ein neues x.

2) \(x^r \not\equiv 1 \text{ (mod p) }\)
dann folgt dass es ein Element aus der Untergruppe q mod p ist. Da q prim, ist \(x^r = g\) also ein Generator der Untergruppe q.