Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

function ops(n) { return Math.exp (((64/9) * (1/3) + 1) * (Math.log(n) * (1/3)) * (Math.log(Math.log(n)) * (2/3))) }

> ops(2*16)

121106.42245436447

> ops(2*32)

38178499.24944067

> ops(2*32) / ops(2*16)

315.24751929508244

So if ops(2*16) costs $8, then ops(2*32) costs $8 * ops(2*32) / ops(2*16) = $2521.98. Far more than $8^2.

The cost reaches the millions for 64 bits, and ~$165 trillion for 128 bits:

> 8 * ops(2*64) / ops(2*16)

5601332.962726709 (far more than $8^2^2)

> 8 * ops(2*128) / ops(2*16)

165647073370.16437 (far more than $8^2^2^2)

Note that this is increasing faster than the number of bits squared:

> ops(2*32) / 32 * 2

37283.690673281904

> ops(2*64) / 64 * 2

20701824.831895076

> ops(2*128) / 128 * 2

153052707259.34015

As the wiki page says, it's super-polynomial in the number of bits.

If you still disagree with all of this, can you explain what's wrong with this method of calculating the worst-case cost of factoring the number n?

Cost(n) = ops(n) * Cost(2^16) / ops(2^16)

Or what you don't understand about this way of calculating it?



Note: Y combinator messed up my formatting in the above example, many asterisks * are supposed to be double asterisks (expoentiation in JS)


->The cost reaches the millions for 64 bits, and ~$165 trillion for 128 bits:

meanwhile 512 bits costs $8

But you just keep believing 128 bits costs $165 trillion ROFL.

>> ops(2 * 16)

>121106.42245436447

>> ops(2 * 32)

>38178499.24944067

>> ops(2 * 32) / ops(2 * 16)

>315.24751929508244

So if ops(216) costs $8, then ops(232) costs $8 * ops(232) / ops(216) = $2521.98. Far more than $8^2.

And I said $256, because as an "embarrassingly parallel" algorithm you get significant benefits from cached results (quickly discard entire number fields that were previously calculated).

Which, btw, is how they break 512bit DH in less than a minute.

Also still a lot closer than your >$165 trillion

sigh


I was going by the example cost of $8 for 16 bits you stated in an earlier comment:

"2^16 = 65536

...

so if a search space of 65536 costs you $8"

If you think the numbers I'm arriving at are wrong then can you specify exactly where my cost function goes wrong?


Their answer:

> So if ops(2*16) costs $8, then ops(232) costs $8 ops(232) / ops(216) = $2521.98. Far more than $8^2. > The cost reaches the millions for 64 bits, and ~$165 trillion for 128 bits:

Your answer

> meanwhile 512 bits costs $8 > But you just keep believing 128 bits costs $165 trillion ROFL.

At this point the only conclusion that doesn't involve questioning your sanity is just to conclude that you don't know anything about math and you struggle even reading mathematical notation (“if <> then <>” being the most basic construct one can learn about math, and you still struggle with it!).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: