[virattara]

Doesn't cracking this problem boil down to finding a pattern in prime numbers, which doesn't seem to exist? For the researchers that think the task is efficiently computable in polynomial time, whats the reason behind their thinking?

[complex_stdnt]

The intuition that the difficulty of factoring comes from the mysteries surround prime numbers is compelling, but it is also somewhat muddied by other known results. For example, a famous result [1] showed that testing whether a given number is prime, actually CAN be done in efficiently (i.e., in polynomial time), unlike integer factorization (that we know of).

Some discussion of why some believe factoring could be easy can be found here: [2]

[1] https://en.wikipedia.org/wiki/AKS_primality_test

[2] https://mathoverflow.net/questions/79366/evidence-for-intege...

[virattara]

Wow, fascinating!