De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} 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
Vragen naar aanleiding van dit antwoord? Klik rechts..!
dinsdag 13 februari 2007
 Re: Discrete logaritme 



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3