Diskrete logaritmen av p-1

[gommle___]

For primtall p, og en primitiv rot g, hva er

[tex]\log_g(p-1) \bmod p[/tex]

?

Mistenker at det er (p-1)/2, men ser ikke helt hvorfor.

[Fibonacci92]

Hva er definisjonen av en primitiv rot?

Hva er definisjonen av den diskrete logaritmen?

[Gommle]

En primitiv rot (for [tex]\mathbb Z_p^*[/tex]) er et gruppemedlem [tex]g[/tex] slik at hele gruppen kan genereres ved multiplikasjon med [tex]g[/tex].

Altså en [tex]g[/tex] slik at [tex]\mathbb Z_p^* = \{g^m,\ 1 \le m \le p-1\}[/tex] for primtall [tex]p[/tex].

Definisjonen av den diskrete logaritmen er:

[tex]\log_g \beta = x \quad \Leftrightarrow \quad g^x = \beta[/tex], hvor [tex]g \in \mathbb Z_p^*[/tex], [tex]\beta \in \mathbb Z_p^*[/tex] og [tex]x \in \mathbb Z_{p-1}[/tex]

[Fibonacci92]

Du vet sikkert også at $p-1 = -1 \mod p$

og at $g^{p-1} = 1$ (Fermat's lille teorem)


Hva skjer om $g^a = 1 $ for $ a < p-1$? Kan g generere hele gruppa da?

For hvilken verdi $x$ må $g^x = -1$ da?

[Gommle]

Hvis [tex]g^a = 1[/tex] for [tex]0 < a < p-1[/tex] så er ikke [tex]g[/tex] en primitiv rot.

Jeg tenker følgende:

[tex](g^x)^2 = 1[/tex] impliserer enten [tex]g^x = 1[/tex] eller [tex]g^x = -1[/tex], men vi vet at [tex]g^x \neq 1[/tex] siden [tex]g[/tex] er en primitiv rot, og dermed impliserer det at [tex]g^x = -1[/tex].

[tex]g^{2x} = 1 = g^{p-1}[/tex]

[tex]2x = p-1[/tex]

Hvis vi da velger [tex]x = (p-1)/2[/tex] impliserer det [tex]g^x = -1[/tex], og dermed er [tex]\log_g(-1) = (p-1)/2[/tex].

Så generelt gjelder vel [tex]\log_\alpha(-1) = \mathrm{ord}(\alpha)/2[/tex] hvor [tex]\alpha[/tex] er en generator med orden [tex]\mathrm{ord}(\alpha)[/tex] i gruppen. (Når jeg tenker meg og er det ikke sikkert at -1 er med i gruppen generert av [tex]\alpha[/tex], så jeg må undersøke litt mer.)

Make sense?