4 ms·

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

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”
        DarkmSparks 2y ago
        opposing side of an argument resorting to a strawman is their implicit admission they were wrong.
        jedwards1211 2y ago
        We're trying to help you understand, and you're stubbornly refusing to swallow your pride and think about what we're saying
      - bmacho 2y ago
        > 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
  - littlestymaar 2y ago
    Do you even read?
    - bmacho 2y ago
      > 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.
    - DarkmSparks 2y ago
      Did you? you linked https://en.wikipedia.org/wiki/General_number_field_sieve 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
      - jedwards1211 2y ago
        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?

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”
      - DarkmSparks 2y ago
        opposing side of an argument resorting to a strawman is their implicit admission they were wrong.
        jedwards1211 2y ago
        We're trying to help you understand, and you're stubbornly refusing to swallow your pride and think about what we're saying
    - bmacho 2y ago
      > 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
- littlestymaar 2y ago
  Do you even read?
  - bmacho 2y ago
    > 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.
  - DarkmSparks 2y ago
    Did you? you linked https://en.wikipedia.org/wiki/General_number_field_sieve 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
    - jedwards1211 2y ago
      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?