Computing integer points on the circumference of a given circle

Question

Is there a known algorithm that efficiently outputs the set of lattice points on the circumference of a given circle? The input circle is specified using its center $(a,b)$ and its radius $r$. The inputs $a, b, $ and $r$ are not necessarily integers.

Answer 1

If $a=b=0$ and $r=pq$ where $p$ and $q$ are primes congruent to 1 mod 4, then from the $O(1)$ integer points on the circle one could determine the factorization of $r$. So the problem is not going to be easier than factorization.

Answer 2

To complement David's answer: if $a$, $b$ and $r$ are all rational then the problem can be translated back to the integer case by multiplying by their common denominator; this may introduce false positives, but since there can be no more than $O(\log r)$ points on the circle then testing them all is no less efficient than the rest of the procedure. And while David notes that the problem is at least as hard as factorization, it's basically exactly as hard as factorization: given a factorization of $r$, it's easy to find all the representations of $r$ as a sum of two squares. First find all the representations of its factors $p=4n+1$ as a sum of two squares, then use the formula for expressing products of sums of two squares as a sum of two squares (along with the 'doubling formula') to find the rest. As far as finding the representation(s) of a prime as a sum of two squares, you might want to see the discussions at https://stackoverflow.com/questions/5380323/whats-the-fastest-algorithm-to-represent-a-prime-as-sum-of-two-squares and https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime .