5 ms·

> (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 != $

by bmacho 2y ago

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

littlestymaar 2y ago
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.
- DarkmSparks 2y ago
  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.
  - littlestymaar 2y ago
    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.
    - DarkmSparks 2y ago
      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.
      - littlestymaar 2y ago
        > 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.
        DarkmSparks 2y ago
        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.
        jedwards1211 2y ago
        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.
  - jedwards1211 2y ago
    The wiki article on GNFS says: > The size of the input to the algorithm is log2 n or the number of bits in the binary representation of n. Any element of the order nc for a constant c is exponential in log n. The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input. "Super-polynomial" means that the running time increases by more than the square. In any case, even if the algorithm were just polynomial, the argument about squaring costs doesn't work out.
cryptizard 2y ago
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).
- deleted 2y ago
  [deleted]
- DarkmSparks 2y ago
  its a cost function, In that case: cost = 2.828^(2*(bits/512)) It didn't "square the cost", it doubled the number of bits to find the cost, I just skipped a load of the math.

by bmacho 2y ago

littlestymaar 2y ago

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.

DarkmSparks 2y ago
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.
- littlestymaar 2y ago
  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.
  - DarkmSparks 2y ago
    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.
    - littlestymaar 2y ago
      > 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.
      - DarkmSparks 2y ago
        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.
        jedwards1211 2y ago
        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.
- jedwards1211 2y ago
  The wiki article on GNFS says: > The size of the input to the algorithm is log2 n or the number of bits in the binary representation of n. Any element of the order nc for a constant c is exponential in log n. The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input. "Super-polynomial" means that the running time increases by more than the square. In any case, even if the algorithm were just polynomial, the argument about squaring costs doesn't work out.

cryptizard 2y ago

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

deleted 2y ago
[deleted]
DarkmSparks 2y ago
its a cost function, In that case: cost = 2.828^(2*(bits/512)) It didn't "square the cost", it doubled the number of bits to find the cost, I just skipped a load of the math.