Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I've written a function that encrypts a text using the RSA algorithm. It then decrypts it using prime factorization, and takes the time it took to decrypt it and puts it in a vector together with the length of the N variable in the RSA algorithm. I do this with a length of N from 28 to 61.

I can then plot this is a graph, and try to estimate how long it would take to prime factorize an N length of 100 or larger.

My problem is that I can find no suitable way to fit my values into a graph that then makes a reasonable approximation of the time it would take for say an N of the length of 100.

I am using Fit and FindFit, but all of my results either end up negative for Length[N] = 100, or they end up something like 2 years, which is not a reasonable answer.

These are my values with the length of N at index 1 and then the time in seconds at index 2.

{{28, 0.016}, {29, 0.}, {32, 0.062}, {33, 0.063}, {36, 0.062}, {37, 
  0.109}, {40, 0.187}, {42, 0.265}, {43, 0.281}, {45, 0.858}, {48, 
  4.04}, {50, 4.805}, {52, 7.941}, {54, 12.512}, {54, 11.497}, {57, 
  19.952}, {60, 103.803}, {61, 102.009}}

I can plot it as follows:

plot = ListPlot[TidN, PlotStyle -> Red];
a1 = a /. FindFit[TidN, a*b^x, {a, b }, x]
b1 = b /. FindFit[TidN, a*b^x, {a, b }, x]
modelplot = Plot[a1*b1^x, {x, 32, 100}, AxesLabel -> {x, y},
   PlotRange -> {{20, 70}, {0, 50}}];
Show[modelplot, plot]

This results in the following:

enter image description here

I then try to estimate the time it would take to factorize the length of an N of 100, like this:

a1*b1^100/(3600*24*365)

This gives the result in years, which isn't reasonable at all. It should, I believe, be more close to 100 years:

0.628951

How can I plot this better, and how can I find a function that estimates large numbers more easily?

I can of course let my computer run and gather more data points from which I can establish a better function perhaps, but should this really be necessary since I already have 18 points to start from?

share|improve this question
1  
What's up with this data point? {29, 0.} –  ssch Nov 20 '12 at 21:27
    
It is a very small number; 0.00565328. –  Daniel B Nov 20 '12 at 21:36
    
Did you post your data points correctly? As @ssch pointed out, the second one at least looks wrong, and the others show a rather odd pattern. I find it unsuprising that a fit to those values gives a result you weren't expecting. Are you getting these results from experimental factorizations? ( I guess that's what you're doing). If so, I think you need a lot more sample runs at each bit length. –  Cuboid Nov 20 '12 at 21:55
3  
You're hoping to extrapolate data in the range of 0 - 100 seconds up to 3 billion seconds? Sounds ambitious... Do you have a theoretical basis for the model you are fitting? –  wxffles Nov 20 '12 at 21:58
3  
Are you sure it's an exponential function? Under the possible issues for FactorInteger is the comment "Timings can increase rapidly and unpredictably with the size of the input". –  wxffles Nov 20 '12 at 22:45
show 4 more comments

1 Answer 1

up vote 3 down vote accepted

Quote from MSieve (one of the more popular factorization programs):

On a fast modern CPU, a 110-digit QS factorization takes nearly 120 hours for Msieve.

A 100-digit one should be significantly less than that. So, no, it does not take 100 years.

The trouble you are having fitting your data is not that there are too few points, but the distribution of the points. The vast majority of the points are basically 0 and only about 5 points occur in a region where the function starts to skyrocket. Nonetheless, we can try fitting it.

According to the notes on internal implementation:

FactorInteger switches between trial division, Pollard, Pollard rho, elliptic curve, and quadratic sieve algorithms.

This is yet another factor that increases the uncertainty of the estimates. It may switch between functions that have different complexities.

Let's assume it uses the quadratic sieve algorithm the whole time. According to the Wikipedia page on L-notation, quadratic sieve runs in $L_n[1/2, 1] = e^{a \log ^{\frac{1}{2}}(n) \log ^{\frac{1}{2}}(\log (n))}$ time, where $n$ is the number we want to factor, and your $x$ values are $\log (n)$.

params = FindFit[pts, b Exp[a n^(1/2) Log[n]^(1/2)], {a, b}, n, MaxIterations -> 2000]

b Exp[a n^(1/2) Log[n]^(1/2)] /. params /. n -> 100
4.47082*10^6

which is a little less than 2 months.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.