3 ms·

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

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.
        DarkmSparks 2y ago
        Firstly, the number of prime numbers < n grows by roughly n/log(n) So moving from 2^16 = 65536 to 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.
        littlestymaar 2y ago
        > if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 “The earth is flat blah blah blah”
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.

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.
      - DarkmSparks 2y ago
        Firstly, the number of prime numbers < n grows by roughly n/log(n) So moving from 2^16 = 65536 to 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.
        littlestymaar 2y ago
        > if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 “The earth is flat blah blah blah”

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.