5 ms·
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.
by fogof 6y 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.
- 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]