I'm not a mathematician by trade so I apologise if this is a dim question. I realise that no such algorithm currently exists but I'm trying to understand what such a polynomial time prime factorization algorithm would look like. My current understanding is that such an algorithm would take less than twice as long to factorise a number twice as large, and instead scale linearly in relation to the bit length of the input. So, for example, an algorithm that performed a single simple operation on every number less than $n(x)$ will not fulfill this criteria, even if $x$ is a very small fraction, nor would one which only needed to perform the cube root of $n$ operations. Am I on the right track?
[Math] What would a polynomial time algorithm for prime factorization do
algorithmscomputational complexityprime factorizationprime numbers
Best Answer
What you described is a linear time algorithm. That is already rather fast (depending on the problem). In a polynomial time algorithm, the time needed for computations grows polynomial in the size of the input. For example, with running time $\mathcal{O}(x^2)$, we would get at most four times the running time when doubling the input size, nine times the time when taking three times the size, etc.
You are right, a linear time algorithm, i.e. $\mathcal{O}(x)$, for factorization is rather unlikely. But maybe there is an algorithm that takes, say, $\mathcal{O}(x^{100})$. This algorithm wouldn't really be applicable in practice on current computers, but it would be a polynomial time algorithm and thus of great theoretic interest.