How to estimate complex algorithm facility requirements?

Question

I'd like to understand how to efficiently estimate hardware requirements for certain complex algorithms using some well known heuristic approach.
Ie. I'd like to estimate quickly how much computer power is necessary to crack my TEA O(2^32) or XTEA O(2^115.15) in some reasonable time or other way round :

Having facility power of a 1000 x 4GHz quad core CPU's, how much time would it take to execute given algorithm?
I'd be also interested in other algo complexity estimations for algorithms like O(log N) etc..

regards bua

Answer 1

Pick whichever answer you like:

1. More than you can afford
2. It would be far, far cheaper to keylog your machine
3. Where are you going to store to 2^20 plaintexts needed to achieve the O(2^115) time complexity
4. A whole bunch

If someone really wants your pr0n collection it is much easier to break the key holder than it is the key.

Answer 2

ok, so I'd came up with some thing like this: Simplifying that CPU clock is this same as MIPS.

having amount of instructions ex. 2^115 and a processor with ex. 1GHz clock
which is:

i = 2^115.15 clock = 1GHz ipersec=1/10e+9

seconds = i * ipersec

in python:

def sec(N,cpuSpeedHz):
    instructions=math.pow(2, N)
    return instructions*(1./cpuSpeedHz)

ex

sec(115.15, math.pow(10,9)) / (365*24*60*60)
1.4614952014571389e+18

so it would take 1.4 ^ 18 years to calculate it

so having 1mln 4 cores 1Ghz processors it would take:

sec(115.15, 1000000*4*math.pow(10,9)) / (365*24*60*60)
365373800364.28467

it would take 3.6 ^ 11 years (~ 3600 mld years)

simplified version:

2^115.15 = 2^32 * 2^83.15 clock = 2^32 ~ 4Ghz 2^83.15 =

>>> math.pow(2,83.15)/(365*24*60*60)
3.4028086845230746e+17

checking:

2^32 = 10 ^ 9.63295986
>>> sec(115.15, math.pow(2,32))/(365*24*60*60)
3.4028086845230746e+17