You mean O(sqrt(n)), not quadratic. And given that the most obvious algorithm there is (check every possible divisor up to sqrt(n)) is O(sqrt(n)) arithmetic ope

You mean O(sqrt(n)), not quadratic. And given that the most obvious algorithm there is (check every possible divisor up to sqrt(n)) is O(sqrt(n)) arithmetic operations, I think it is fair to say this is not an important result. I suppose it is a constant factor better than sqrt(n). But tricks along these lines go back to Gauss, at least. Edit: ah I see, they claim O(n^2). Well I've never had an O(n^2) primality test before. I will put that in my kit of "do-not-ever-use-this" tools, just in case all my other ones break.