3 ms·
Factoring via Graph Three-Colouring
- braythwayt 11y agoA really easy-to-follow argument that piqued my intellectual curiosity: By transforming a binary multiplication into a big circuit, you also have a big graph where a proper coloring represents correct factorization of the result. Thus, the problem of coloring that particular graph is as hard as the problem of factoring the result of the multiplication. Therefore, the general problem of colouring graphs may be easy for many cases, but is hard for specific cases, and we can construct those cases by taking hard-to-factor numbers and turning them into graphs. I love these kinds of demonstrations, they are easy to follow for the non-specialist and demonstrate the beauty of mathematics and reasoning.