3 ms·
>you need to check 2^903 edge colorings This instantly reminded me of the "It will never be possible to brute force AES256 (Check 2^256 possibilities) because,
by bauruine 4y ago
>you need to check 2^903 edge colorings
This instantly reminded me of the "It will never be possible to brute force AES256 (Check 2^256 possibilities) because, even in the best case, it needs more energy than the whole Solar system contains" [0] The author states that 2^903 should be possible to do in less than a year. Am I wrong and those aren't related problems? Or is the author a bit optimistic?
[0] https://security.stackexchange.com/a/6149 https://security.stackexchange.com/a/6149
- penteract 4y agoThe problem has plenty of symmetry and there are ways to solve it other than naive brute force. For example, the proof that R(3,3)=6 is given in the first part of the article, and does not involve listing 2^15 graphs. This also could apply to AES256 - if it has some mathematical structure that can be exploited, then brute forcing might not be needed to break it - see https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Known_attacks https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#K... .
- bauruine 4y agoTrue but the last part of the article is basically only about the computation and not about mathematical breakthroughs. And from that point of view both numbers are equally infeasible to compute right?