Introduction to Cryptography II

So in order to defeat RSA encryption we simple need to factor the modulus n into it's two prime factors, so what the big deal ?

Answer: factoring a number into its prime constituants is hard!

(* Lets make a table of ever larger prime numbers *)

ptable=Table[Prime[10^r],{r,1,12}]
qtable=Table[Prime[8^r],{r,1,12}]

(* construct the modulus n = p q, and then factor it using the FactorInteger routine in Mathematica. Time how long it takes to do this *)

timer[i_]:=Module[{t,p,q,n},p=ptable[[i]];q=qtable[[i]];n=p q;
t=Timing[FactorInteger[n]];{N[Log[n]],Log[t[[1]]]}]

table=Table[timer[i],{i,1,12}]

line=Fit[table,{1,x},x]

Show[ListPlot[table,PlotStyle->{Red,PointSize->0.025}],Plot[line,{x,1,55}],AxesLabel->{Log[n],Log[t]},PlotRange->All]