Re: Discrete logaritme

Dit is een reactie op vraag 49207

Hartelijk bedankt voor deze eerste stap. X moest inderdaad (p-1)/2 zijn. De beredenering gaat me echter net 1 stap te snel. P is oneven en p-1 is even, daar had ik ook al in gezocht. Echter, de volgende stap snap ik niet helemaal.

a=2^((p-1)/2), ik neem aan dat dit een aangepaste versie is van 2^(p-1) mod p, die gelijk moet zijn aan 1. Echter de deling door 2 snap ik niet.
"er geldt dan a^2=1", dat is weer terug uit de oude definitie lijkt mij.
"en dus a=1 of a=-1 (mod p)"
dat volg ik dan wel
"Er geldt a=-1."
alleen waarom er dan geldt dat a=-1 en hoe dat belangrijk is snap ik niet, want het was toch al voldoende dat a=1?

Bram
Student universiteit - dinsdag 13 februari 2007

Antwoord

Omdat (P-1)/2 geheel is staat daar gewoon een macht van 2 en a²=2^p-1=1; alles gaat hier (mod p). Als we kunnen bewijzen dat a=-1=p-1 (mod p) dan zijn we klaar want je wilde 2^x=p-1=-1 (mod p) oplossen, de oplossing is dan (p-1)/2. Ik realiseerde me echter dat het niet altijd mogelijk is: neem p=7 dan zijn dit de machten van 2 (mod 7): 2, 4, 8=1 en dat zijn ze. De vergelijking 2^x=6 heeft (mod 7) geen oplossing. Het hangt dus ook nog van p af of het eigenlijk wel kan.

kphart
dinsdag 13 februari 2007

©2001-2024 WisFaq