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 a²=1 en dus a=1 of a=-1 (mod p). Er geldt a=-1.

kphart
dinsdag 13 februari 2007

Re: Discrete logaritme

©2001-2024 WisFaq