Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

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-2024 WisFaq