WisFaq!

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 Dogger
4-2-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 = 2⁵⁰. Delen van r door alle getallen 1,2,..,2⁵⁰ duurt dan 2⁵⁰ microseconden, dat is ongeveer 35·7 jaar.
Het heeft dus niets met het algorithme van Euclides te maken.

hr
12-2-2004