Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com