Svar Före-läsningsuppgift 7

En enkel metod att faktorisera ett tal n = pq är att testa att dela med alla tal mindre än \sqrt{n}. Arbetsinsatsen för att göra det är då ungefär proportionell mot \sqrt{n}. Om det tar 1 minut att genomföra detta på ett tal av storleksordning 10^{20} tar det alltså ungefär \sqrt{10^{40}}/\sqrt{10^{20}} = 10^{10} minuter att göra det på ett tal av storleksordning 10^{40}. Omräknat blir detta ca 20000 år.


Notera dock att detta är ett långsamt sätt att faktorisera tal på. Kontorsdatorn klarade, med hjälp av Mathematica, av att faktorisera ett tal på storleksordningen 10^{60} på strax under en minut. Faktoriseringsrekordet ligger på ungefär 10^{230}. I praktiken använder man nyklar på storleksordningen minst 10^{600} i RSA.

Senast modifierad: torsdag, 17 april 2014, 15:43