It's very rare for something to scale sublinearly in the number of bits :-)
complexity(2∗∗1024)/complexity(2∗∗762) comes out to about 1500x more work.
complexity(2∗∗1024)/complexity(2∗∗762) comes out to about 1500x more work.
So to correct myself, the difficulty factor is 1400 to 1500, and here's the modified Python program, using the simplest change I could:
#!/usr/bin/python
from math import *
ln = log
def complexity( n ):
lnn = ln(2**n)
return exp( \
(64./9)**(1./3) * \
(lnn**(1./3)) * \
(ln(lnn)**(2./3)) \
)
print complexity(762)
print complexity(1024)
print complexity(1024)/complexity(762)
That's not the fastest or best way to compute this, but it's the smallest and cleanest change I could get away with that reflects how I think about this, which is number of bits. A reasonable alternative is in the parent comment to this one. lnn = n * ln(2)But you're right, it would otherwise be an appropriate simplification.