23 ms·
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.
by malft 8y ago
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.
- deleted 8y ago[deleted]
- ColinWright 8y agoYou are absolutely right - I was misled by the page I referred to using "n" as the number being factored, and not the size of the problem, which is log_2(n). 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.
- jwilk 8y agoThis should be slightly more efficient: lnn = n * ln(2)
- ColinWright 8y agoIt is, but not everyone is comfortable with why that is true, hence leaving it the way I did. But you're right, it would otherwise be an appropriate simplification.