4 ms·
note, for people who were briefly confused like me, that to be considered polynomial time, it has to be polynomial in the number of bits, i.e. log(N).
by currymj 6y ago
note, for people who were briefly confused like me, that to be considered polynomial time, it has to be polynomial in the number of bits, i.e. log(N).
- fogof 6y agoThe abstract says "computes the prime factorisation of a positive integer N", so it's not your fault you were confused. The abstract should be corrected.
- anderskaseorg 6y agoThere’s nothing wrong with the abstract as written. It makes no claim that the algorithm is polynomial-time.
- archgoon 6y agoThe abstract is correct. A positive integer N is log(N) bits long. If X = log(N), than a algorithm that runs in N^(1/5) will run in 2^(X/5) time.
- deleted 6y ago[deleted]
- rubatuga 6y agoYep, this can be considered pseudo-polynomial time.