Comment on An exponent one-fifth algorithm for deterministic integer factorisationComments−currymj5ynote, 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).−rubatuga5yYep, this can be considered pseudo-polynomial time.−fogof5yThe 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.−archgoon5yThe 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.−anderskaseorg5yThere’s nothing wrong with the abstract as written. It makes no claim that the algorithm is polynomial-time.
Comments
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).
Yep, this can be considered pseudo-polynomial time.
The 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.
The 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.
There’s nothing wrong with the abstract as written. It makes no claim that the algorithm is polynomial-time.