Elliptische Kurven < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Ich gucke mir gerade einen Algorithmus an, um diskrete Logarithmen in der Punktgruppe von elleiptischen Kurven zu berechnen.
http://www.cs.nctu.edu.tw/~rjchen/ECC2009/18_Pohlig-Hellman.pdf (Seite 4).
Mir ist hier alles klar, außer bei (5) wie man im Nenner auf das [mm] q^2 [/mm] (^.-)
Zunächst hat man ja die Gleichung [mm] \frac{N}{q}Q=k_0 \cdot \frac{N}{q}P, [/mm] wobei das [mm] k_0 [/mm] aus der p-adischen Zahlendarstellung von k kommt. Mit dieser Gleichung bestimmt man also das [mm] k_0. [/mm] Ist dies getan, muss man ja nach (4) [mm] Q_1 [/mm] berechnen, was man mittels des bekannten [mm] k_0 [/mm] P tut. Aber wie gesagt, bei Schritt (5) haperts dann, wo da dieses [mm] \frac{N}{q^2} [/mm] herkommt?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:15 So 14.08.2011 | | Autor: | felixf |
Moin!
> Ich gucke mir gerade einen Algorithmus an, um diskrete
> Logarithmen in der Punktgruppe von elleiptischen Kurven zu
> berechnen.
Der Algorithmus funktioniert auch in allgemeinen (endlichen) Gruppen.
> http://www.cs.nctu.edu.tw/~rjchen/ECC2009/18_Pohlig-Hellman.pdf
> (Seite 4).
>
> Mir ist hier alles klar, außer bei (5) wie man im Nenner
> auf das [mm]q^2[/mm] (^.-)
>
> Zunächst hat man ja die Gleichung [mm]\frac{N}{q}Q=k_0 \cdot \frac{N}{q}P,[/mm]
Genau, oder anders gesagt: der diskrete Logarithmus von $Q$ zur Basis $P$ modulo $q$ ist [mm] $k_0$.
[/mm]
> wobei das [mm]k_0[/mm] aus der p-adischen Zahlendarstellung von k
> kommt. Mit dieser Gleichung bestimmt man also das [mm]k_0.[/mm] Ist
> dies getan, muss man ja nach (4) [mm]Q_1[/mm] berechnen, was man
> mittels des bekannten [mm]k_0[/mm] P tut. Aber wie gesagt, bei
> Schritt (5) haperts dann, wo da dieses [mm]\frac{N}{q^2}[/mm]
> herkommt?
Es ist doch $(x [mm] q^2 [/mm] + [mm] k_1 [/mm] q + [mm] k_0) [/mm] P = Q$, wobei du $x$ noch nicht kennst, [mm] $k_0$ [/mm] gerade berechnet hast und [mm] $k_1$ [/mm] als naechstes herausfinden willst.
Wenn du jetzt [mm] $k_0 [/mm] P$ auf beiden Seiten abziehst, steht da $x [mm] q^2 [/mm] P + [mm] k_1 [/mm] q P = Q - [mm] k_0 [/mm] P$. Wenn du die Gleichung jetzt mit [mm] $\frac{N}{q^2}$ [/mm] multiplizierst, hast du da $x N P + [mm] k_1 \frac{N}{q} [/mm] P = [mm] \frac{N}{q^2} [/mm] (Q - [mm] k_0 [/mm] P)$ stehen, und da $N P = 0$ ist und $Q - [mm] k_0 [/mm] P = [mm] Q_1$ [/mm] steht da also [mm] $k_1 (\frac{N}{q} [/mm] P) = [mm] \frac{N}{q^2} Q_1$.
[/mm]
Wenn du die Gleichung mit [mm] $\frac{N}{q}$ [/mm] multipliziert haettest, staend da $0 = [mm] \frac{N}{q} Q_1$, [/mm] was dir nicht viel bringt wenn du [mm] $k_1$ [/mm] bestimmen willst. Und wenn du sie mit [mm] $\frac{N}{q^3}$ [/mm] multipliziert haettest, staend da $x [mm] \frac{N}{q} [/mm] P + [mm] k_1 \frac{N}{q^2} [/mm] P = [mm] \frac{N}{q^3} Q_1$, [/mm] und du haettest $x$ noch in der Gleichung.
Deswegen multipliziert man also mit [mm] $\frac{N}{q^2}$ [/mm] und es bleibt da nachher ein [mm] $\frac{N}{q^2}$ [/mm] vor [mm] $Q_1$ [/mm] stehen.
LG Felix
|
|
|
| |
|
Vieeeelen Dank, klingt einleuchtend :D :D
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:18 So 14.08.2011 | | Autor: | felixf |
PS: Ich hab den Thread mal aufgespalten und diesen Teil ins Krytpographie-Forum verschoben, da der Pohlig-Hellman-Algorithmus dorthin gehoert. Der urspruengliche Thread findet sich hier.
|
|
|
|
