I know that there is already a similar question asked on here, but after reading the wiki page on trial division, I am confused, and the other answer doesn't help. The wiki page states that when doing trial division, "If a variant is used without primality testing, but simply dividing by every odd number less than the square root the base-2 n digit number a, prime or not, the algorithm can take up to about 2^(n/2) time".

Using such a variant, however, why wouldn't the time complexity be O(sqrt(n)) in the worst case? In the worst case you check all the numbers up to sqrt(n). So in the worst case, the algorithm would depend on the sqrt of the number of natural numbers before n, no? Also, would a variant that divides a number n by every natural number less than n until a factor is found in order to determine if n is prime is used be linear in time?

Link to the wiki I'm talking about: https://en.wikipedia.org/wiki/Trial_division (Quote pulled from the section titled, "Speed")

Side Question: Is this post better suited here as a new post, or should I have posted this question as a follow up to the other, similar question on trial division that was posted 4 years ago on here? I'm new here so I'm not sure what's preferred.

  • $\begingroup$ The "n" you're using is the input length, in your case, the number of digits needed to represent the input number. If you represent the problem in unary version, i.e. use 1^n to represent the number, then according to padding argument, this algorithm could be O(sqrt(n))-time. $\endgroup$ – Taylor Huang Jun 9 '19 at 4:28
  • $\begingroup$ @TaylorHuang Actually, it would still be linear time because you'd have to read the whole input to find out what $n$ is. $\endgroup$ – David Richerby Jun 9 '19 at 8:25
  • $\begingroup$ Ideally, you'd post a comment on the other question, asking about the part that you don't understand. However, new users can't post comments (otherwise, unfortunately, we'd get flooded with spam), so that wasn't an option. Having said that, you are just repeating an old question, saying you don't understand the answers there but not giving us any clue about what you don't understand. That doesn't help us to help you. $\endgroup$ – David Richerby Jun 9 '19 at 8:28