De digitale vraagbaak voor het wiskundeonderwijs

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

HOME

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

inloggen

colofon

  \require{AMSmath} Printen

Schatting van de tijd nodig om een code te ontcijferen

Stel: als we een geheime boodschap voorstellen als een groot priem getal p, dan kunnen we de volgende boodschap versturen: r = p · q, waar q $>$ p ook een priemgetal is en de de encryptie sleutel moet voorstellen.

Kijk voor elk geheel getal p 1$<$ p $<$ r of p deelbaar us door r. Als dat zo is, dan drukken we af: 'P is de geheime boodscha'p'.

Stel dat iemand dit algoritme gebruikt, en een computer heeft die in 1 microseconde twee getallen van 100 bits door elkaar kan delen.

Geef een schatting van de tijd die (in het meest ongunstige geval) nodig is om de code te ontcijferen als de geheime boodschap 100 bits bevat.

Een bij vraag: kan ik hier het algoritme van Euclides voor gebruiken?

Barry
Student universiteit - woensdag 4 februari 2004

Antwoord

De vraag bevat enkele onnauwkeurigheden. Ik neem aan dat u bedoelt "r deelbaar door p", verder dat r 100 bits bevat en dat een poging om r door een kleiner getal te delen 1 microseconde duurt (dat is 10-6 seconde).
In het ongunstigste geval zijn p en q allebei ongeveer Ör = 250. Delen van r door alle getallen 1,2,..,250 duurt dan 250 microseconden, dat is ongeveer 35·7 jaar.
Het heeft dus niets met het algorithme van Euclides te maken.

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
donderdag 12 februari 2004



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3