Übung 10 Aufgabe P1 a

Benutzeravatar
itportal2
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 25. Jan 2008 15:34
Wohnort: Darmstadt

Übung 10 Aufgabe P1 a

Beitrag von itportal2 » 11. Feb 2013 15:29

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
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 6. Mär 2011 14:01

Re: Übung 10 Aufgabe P1 a

Beitrag von dees » 11. Feb 2013 17:47

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.

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: Übung 10 Aufgabe P1 a

Beitrag von olg » 11. Feb 2013 18:03

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).
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

Benutzeravatar
itportal2
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 25. Jan 2008 15:34
Wohnort: Darmstadt

Re: Übung 10 Aufgabe P1 a

Beitrag von itportal2 » 11. Feb 2013 18:43

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.

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: Übung 10 Aufgabe P1 a

Beitrag von olg » 11. Feb 2013 19:06

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.
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

Antworten

Zurück zu „Archiv“