Hacker News new | ask | show | jobs
by fogof 2058 days ago
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.
2 comments
archgoon 2058 days ago
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.
link
anderskaseorg 2058 days ago
There’s nothing wrong with the abstract as written. It makes no claim that the algorithm is polynomial-time.
link