Hacker News Reader

Comment by DarkmSparks | Hacker News Reader

thats linear search

in gnfs the search space is number fields, so you increase the number of the number fields by the square of what came before.

View on HN

Right, so if it costs $8 to search the space for a 16-bit key, a proper equation for the cost of cracking an n-bit key is

Cost(n) = search_space(n) * $8 / search_space(16)

And search_space(x) = 2^x so

Cost(n) = 2^n * $2^3 / 2^16 = $2^(n - 13)

Cost(32) = $2^(32 - 13) = $524288 Cost(64) = $2^(64 - 13) = $2251799813685248

So it quickly becomes astronomically expensive.

If you double the number of bits n you get

Cost(2n) = $2^(2n - 13)

You were assuming that Cost(32) = Cost(16)^2, in other words Cost(2n) = Cost(n)^2. But this equality doesn't hold:

Cost(n)^2 = $2^(n - 13)^2 = $2^(2n - 26)

This is significantly smaller than Cost(2n) = $2^(2n - 13) as stated above.

An equation with different units on each side like "512 bit = $8" doesn't work mathematically and will lead to contradictory conclusions.

Firstly, the number of prime numbers < n grows by roughly n/log(n)

So moving from 2^16 = 65536

2^32 = 4294967296

Increases the size of the total potential search space from 5909 to 193635251, which is ~ 5909 x 32769

secondly, the reason it grows by only n^2, is you only need to search along the curve n = a x b - which is the "sieve" part.

if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64

Thirdly, your stupidly high costs are because you seem to think you need to check if 4817 x 5693 is a prime fractorisation of 26768069 when in fact you already know the prime factorisation by that point.

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64

“The earth is flat blah blah blah”

opposing side of an argument resorting to a strawman is their implicit admission they were wrong.

We're trying to help you understand, and you're stubbornly refusing to swallow your pride and think about what we're saying

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64

Can you answer

    a) If 1 apple costs you 8$ then (1)^2 apple costs you: ???
    b) If 10 apples cost you 8$ then (10)^2 apples costs you: ???

edit: between the price and the amount, usually there is a ~linear relationship. So if you can buy 2^512 something for 8$, then chances are that for 8 times the price you'll only get ~8 times more amount, and not 2^512 times more

the ^2's are

https://en.m.wikipedia.org/wiki/Big_O_notation

The tldr is bigO gives you how the cost of apples changes with the number of apples in the worst case.

its a rough simplification, the precise formula is close but not exactly that. the simplification is also actually (2n)^2 but in my defense I was going from memory of work from more than 2 decades ago (testing generated prime factors were good prime factors, overwhelmingly they were not).

using your apples example if the bigO of eating apples is O(n^2), and it takes you 8 minutes to eat 2 apples, it will take you no more than 64 minutes to eat 4 apples.

Okay I hadn't read about how many calculations it takes to cover the search space, so my equations aren't right about that.

However, you will do yourself a big favor if you take the time to understand why this is wrong:

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64

The cost per calculation is some constant C:

Cost(n calcs) = n calcs * C

Therefore,

Cost(n^2 calcs) = n^2 calcs * C

In this example, C = $8 / 2^512 = $2^-509

So Cost(2^512^2) = Cost(2^1024) = 2^1024 * $2^-509 = $2^425

I wouldnt argue with a claim of $2425 tbh.

The $8 will vary, and the actual cost function completely depends on the implimentation, its definitely possible to do worse, very likely possible to do better - there was rumors a few years ago that some Riemann surface based math can do it in O(1), but I know nothing about Riemann surfaces so can't judge their veracity.

Do you even read?

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64

This and the stuff they've been writing about suggest that we are observing a mind that used to know things, but suffered some serious damages/degrade over time. That's always so sad.

Did you? you linked https://en.wikipedia.org/wiki/General_number_field_sieve

already That gives the worst case complexity right at the top.

> 2^16

[1] 65536

> n<-2^32

> exp(((64/9)^(1/3)+1)(log(n)^(1/3))(log(log(n))^(2/3)))

[1] 38178499

> 38178499/65536

[1] 582 2^16 -> 2^32 ~ x 2^9

> n<-2^64

> exp(((64/9)^(1/3)+1)(log(n)^(1/3))(log(log(n))^(2/3)))

[1] 84794674511

> 84794674511/38178499

[1] 2221

2^32-> 2^64 ~ x 2^11

> n<-2^128

> exp(((64/9)^(1/3)+1)(log(n)^(1/3))(log(log(n))^(2/3)))

[1] 2.507616e+15

> 2.507616e+15/84794674511

[1] 29572

2^64 -> 2^128 ~ x 2^15

So in GNFS 2^32 -> 2^64 complexity doesn't increase 4294967296 times, worst case it increases 2221 times

_In practice_ the cost grows closer to (nbits)^2 mostly because as an "embarrassingly parallel" algorithm you get significant benefits from cached results (quickly discard entire number fields that were previously calculated).

if O(x) = 8 then O(x)^2 = 8^2

I did miss a x2 earlier because e.g. 128 bits is 128^2 (16384 rather than 29572) harder than 64 bits, not 64^2

So its (2xO(x))^2 = (2 x 8)^2 = $256

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?

->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

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!).

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?

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

You still cannot take the square of a dollar count… What don't you understand.

You're trying to seek refuge in math you barely understand to escape contradiction but it's not even a problem with GNFS, the fundamental problem is that you're trying to do something you mathematically cannot do, which is squaring sums of money. It's equivalent to a division by zero in a demonstration, it just nullifies all the reasoning around it.

And I've given plenty of illustrations why you cannot do that you definitely should read instead of obsessing yourself in proving you're right.

Reply on news.ycombinator.com