\require{AMSmath}
WisFaq - de digitale vraagbaak voor wiskunde en wiskunde onderwijs


Printen

Discrete logaritme

I.v.m. een opdracht was ik bezig om een discrete logaritme te vinden van een getal y (de oplossing van f(x)=y) waarbij f(x)=2^x mod p, en p een enorm lang priemgetal is.

Nou is dit voor bijna alle waarden van y zeer moeilijk te vinden, maar zou dit voor y=p-1 heel makkelijk te bepalen moeten zijn. Ik kom er zelf echter niet uit. Brute force rekenen mag dus niet de oplossing zijn (daarnaast bestaat p uit 35 cijfers, dus het is vrijwel ondoenelijk). Er moet dus een makkelijke methode zijn waarmee het eenvoudig te bepalen is. Ik heb de oplossing geprobeerd te zoeken in de stelling dat 2^(p-1) mod p = 1 (dit geldt voor alle priemgetallen), maar ik kom er daar ook niet mee uit.

Bram
Student universiteit - dinsdag 13 februari 2007

Antwoord

p is oneven, dus p-1 is even. Bekijk a=2(p-1)/2, er geldt dan a2=1 en dus a=1 of a=-1 (mod p). Er geldt a=-1.

kphart
dinsdag 13 februari 2007

 Re: Discrete logaritme 

©2001-2021 WisFaq