Hacker News Reader

Comment by complex_stdnt | Hacker News Reader

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.

View on HN

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?

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...

Wow, fascinating!

Maybe there is something I don't get, but N ^ 1/5 looks polynomial to me. Even quite small polynome power!

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.

Reply on news.ycombinator.com