Hacker News new | ask | show | jobs
by complex_stdnt 2052 days ago
I'm a PhD student who studies stuff similar to this (I work in complexity theory), and one of my favorite "conversation starters" when I meet other researchers is whether they think integer factorization is actually a computationally difficult task.

Perhaps surprisingly, most people don't have strong feelings either way, and a good number of researchers suspect the task is actually efficiently computable (i.e., in polynomial-time). At least from the standpoint of complexity theory there are not really any compelling reasons to think factoring is hard, beyond the fact that we haven't discovered an algorithm for it yet.
2 comments
virattara 2052 days ago
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?
link
complex_stdnt 2051 days ago
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...

link
virattara 2050 days ago
Wow, fascinating!
link
pierrebai 2052 days ago
Maybe there is something I don't get, but N ^ 1/5 looks polynomial to me. Even quite small polynome power!
link
complex_stdnt 2052 days ago
So in integer factorization there are two different quantities that one might naturally want to denote by N: the number you want to factor and the number of bits required to specify that number (i.e, the input length).

The convention is to let N be the number to be factored, in which case log_2(N) is the input length. Hence, an algorithm that runs in time "polynomial (in the input length)" would have to run in time log(N)^k for some k.

link