Hacker News new | past | comments | ask | show | jobs | submit login

> (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64)

What can you square then? For example, can you square lengths? E.g. 1km is 1000m, what is its square?






That is because "square length" is its own unit, which we call area. Square money is not meaningful as a unit, that is the problem. You can square anything you want but it turns it into a different unit, which the original commenter did not do (they presumed squaring dollars still gives you dollars back).

1km² aka 1,000,000m², note how the resulting units aren't km and m but square kilometers and square meters.

> What can you square then?

In that case it's the number of operations (which is unitless) that must be squared and then multiplied by the cost of each operation. For instance (figures are completely made up for illustration purpose) if one individual operation costs 0.1 cent, and you have 8000 ops for the factorization, it costs $8, and the operation number squared means you have 64,000,000 operations, and the total cost is $64k. In practice we're talking about trillions of very cheap operations but when you square that number you get an insanely big number which even multiplied by a small individual cost ends up costing trillions of dollars, putting it out of reach of factorization from anyone.


the search space is p1×p2 = cost therefore

(p1^2) x (p2^2) = (p1xp2)^2 =cost^2

and gnfs search cost increases in cost by (roughly) the square of the number of bits.


I'll keep trying to explain it to you: you cannot take the square of a price.

If my Yuan exchange rate example didn't convince you, let's have a few thoughts experiments:

- let say you can do can do some amount of work for less than $1 (maybe even factoring a 512 bits number) let's call that amount of work X, and you do it for say $0.9. Do you think you can do X² work for price^2, which is $0.81 ? Yes, much more work for less than the price of doing X, isn't that magical?

- a hard drive with 1TB of storage costs $40. Do you think you can have 1 Yottabyte (10^12 squared is 10^24) of storage for just $1600?

There's a reason to all these paradoxes, it simply makes no sense to take the square of a sum of money, because you can't pay it in square dollars.


every time you double the number of bits, you increase the search space by the square of what came before

2^16 = 65536

2^32 = 4294967296

4294967296/65536 = 65536

so if a search space of 65536 costs you $8, then a search space of 4294967296 = 65536 x 65536 = 8 x 8 = 8^2 = $64

2^64 = 1.844674e+19

1.844674e+19/4294967296 = 4294967296

so a search space of 1.844674e+19 = 4294967296 x 4294967296 = 65536 x 65536 x 65536 x 65536 = 8 x 8 x 8 x 8 = 8^2^2 = 8^4 = $4096

where here $8 is the cost of finding (or not) 1 number in a haystack of 2^512 numbers, and the rest is identical.


> so if a search space of 65536 costs you $8, then a search space of 4294967296 = 65536 x 65536 = 8 x 8 = 8^2 = 64

So close, yet so far: the correct answer here is “65536 x 8 = $525k”, not “8x8 = $64”. If a $8 worth of hard drive can store 65536, then to store 4294967296 you need 65536 of such drives, not 8…

Man this is really embarrassing.


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.




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

Search: