Orders of Magnitude
This page answers frequently asked questions about
execution times and orders of magnitude.
- Time required to do algorithm X on problem Y
- Effect of faster computers on algorithm X
- How big is 2n?
- Crossover of nx and 2n
Time required to do algorithm X on problem Y
This table comes from "Computers and Intractability, a guide to the Theory
of NP-Completeness", Micheal R. Garey & David S. Johnson, pg 7. Across is
the number of items being operated on, down is the complexity of an algorithm
operating on that many items. Each operation takes .000001 seconds.
|n ||.00001 sec||.00002 sec||.00003 sec||.00004 sec||.00005 sec||.00006 sec
|n2||.0001 sec||.0004 sec||.0009 sec||.0016 sec||.0025 sec||.0036 sec
|n3||.001 sec||.008 sec||.027 sec||.064 sec||.125 sec||.216 sec
|n5||.1 sec||3.2 sec||24.3 sec||1.7 min||5.2 min||13.0 min
|2n||.001 sec||1.0 sec||17.9 min||12.7 day||35.7 yrs||366 cen
|3n||.059 sec||58 min||6.5 yrs||3855 cen||2x108 cen||1.3x1013 cen
Effect of Faster Computers on algorithm X
Here is another table from the same source, page 8. Across is the type
of computer, down is the algorithm being run, the data points are the number
of items in the largest problem that can be solved in an hour.
|Present Computer||100x faster||1000x faster
How big is 2n?
How long would it take to guess n bits? How long would it take to
brute-force search through 2n possibilities? How big is 2n?
256-bit keys (32 bytes) are probably good enough to thwart brute-force
search forever; 512-bit keys certainly are.
- That's 4, the number of items a human can track simultaneously.
- That's 256, the number of possible values for a byte.
- That's 8192 or 8K, and it fits in the on-chip cache.
- 65,536 is 64K, the size where MS-DOS has trouble
with contiguous allocations.
- 4,294,967,296 is 4000 meg or 4 gig. It's the
point where 32-bit counters will wrap around. It's the amount of RAM
in my current machine. countx 32 5 is a
random number test of 232 4-byte values and takes 103
seconds on my 1.86GHz Intel machine.
- The number of keys one must check to crack any exportable
crypto by brute-force.
- "The first experimental cryptanalysis of the Data Encryption
Standard" by Mitsuru Matsui, CRYPTO 94. Matsui used 243 plaintext/ciphertext
pairs to deduce the key for DES.
- The maximum length random number sequence I've
ever tested on my home machine. Took a month.
- 5000 MIPS-years, the number of instructions executed
in the factoring of RSA-129.
ftp://ftp.ox.ac.uk/pub/math/rsa129/rsa129.ps.gz for more details.
RSA-129 was the phrase THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE and it
was encrypted using RSA and a 429-bit (129-decimal digit) composite number.
- Avogadro's number. The number of carbon atoms
in 12 grams of coal.
- An estimate of the total number of instructions
executed by all of humanity in all of history up to 2008. According
to sci.crypt quoting Odlyzko, about 272 instructions were
executed in 1993 and 1994 together. According to Moore's law,
processing power doubles every two years. So that's 273
cycles total by 1994, and add one to the exponent for every two years
- The number of atoms in a cubic meter of water.
- The number of possible keys for IDEA.
- Instructions per second for a 1-meter-cube nanocomputer.
If a nanotech computer has atoms packed as densely as water, each atom
occupies about 10-10 meters. If each processor has a
million atoms and is a cube, that's 100x100x100 atoms, so each
processor is 10-8 meters across. If processors run at the
speed of light, light travels 108 meters per second, so the
processor should execute 1016 instructions per second. A
1-cubic meter computer would contain 1023 processors and do
1039, or 2129, instructions per second.
- Number of atoms in the planet. From Bruce
Schneier's "Applied Cryptography", first edition.
- Number of atoms in the sun. Applied Cryptography again.
- Possible 256-bit (32-byte) keys.
- Instructions executed by a nanocomputer the
size of the sun running for a million years. 2190 atoms /
220 atoms/processor * 1016 instructions/second *
- Possible 512-bit (64-byte) keys.
Crossover for nx and 2n
This table shows when 2n becomes bigger than
nx, for various n.
This suggests that 2n is faster than n11 for all problems requiring less
than 264 operations (that is, all currently feasible problems).
Hash Functions and Block Ciphers
Random Number Results
Computing the HOMFLY polynomial for knots
Table of Contents