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.
Diskrete logaritmen av p-1
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Abel
- Innlegg: 665
- Registrert: 27/01-2007 22:55
Hva er definisjonen av en primitiv rot?
Hva er definisjonen av den diskrete logaritmen?
Hva er definisjonen av den diskrete logaritmen?
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]
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]
http://projecteuler.net/ | fysmat
-
- Abel
- Innlegg: 665
- Registrert: 27/01-2007 22:55
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?
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?
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?
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?
http://projecteuler.net/ | fysmat