Recently, I've been working towards implementing the Sieve of Atkin with significantly better performance than the version found on Wikipedia.
From reading the original paper (http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf), it seems the author takes a different approach than Wikipedia: whereas Wikipedia's code is attempting to find solutions to each quadratic form by testing all possible values of x and y, the author instead (see page 1026, Algorithm 4.1-4.3 in the paper linked above) does the following:
If we are trying to sieve primes out of numbers in the range [L, L+B) (i.e., the arithmetic progression of B numbers starting at L), he considers the annulus described by each quadratic form (take $4x^2 + y^2$ for instance):
$60L \le 4x^2 + y^2 < 60L + 60B$
He then provides an algorithm which should enumerate all triples (x, y, k) for which: $4x^2 + y^2 = 60k + \delta$
My question is regarding this algorithm. Although the paper treats it as such, it is not obvious to me why we have the restriction (x mod 15, y mod 30), or how f and g are picked - he says in the description of the algorithm:
Given positive integers $\delta < 60$, $f \le 15$, and $g \le 30$ such that $\delta \equiv 4f^2 + g^2$ (mod 60), ...
Does this mean that we can simply pick one particular pair (f, g) for which the congruence holds, or if more than one pair exists does one need to enumerate over all pairs in order to generate all triples (x, y, k)?