Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
add comment

1 Answer

For Algorithm 4.1 $f,g,\delta$ are givens, considered pre-specified. Then for the given $f,g$ it iterates over all $x\equiv f \pmod{15}$ and $y\equiv g \pmod{30}$ that are of appropriate size for the $[60L,60(L+B)]$ bounds. For each such $(x,y)$ $$ 4x^2+y^2 = 4(15u+f)^2+(30v+g)^2 \equiv 4f^2+g^2 \equiv \delta \pmod{60} $$

This algorithm is used to execute step 2 for Algorithm 3.1 and will need to be performed once for each $(f,g)$ that satisfy $4f^2+g^2 \equiv \delta \pmod{60}$ for the given $\delta$. For each choice of $\delta\in \{1,13,17,29,37,41,49,53\}$ there are 16 possibilities for $(f,g)$ that yield solutions, e.g. for $\delta=1$ we have to consider $(f,g) \in \{(2,15),(3, 5),(3, 25),\ldots,(15, 29)\}$.

So for the purposes of Algorithm 4.1 $(f,g)$ is considered fixed, but for the purposes of the sieve, at step 2 of Algorithm 3.1 where it asks "For each $(x,y,k)$" you do need to iterate over all suitable pairs to find them all.

share|improve this answer
    
Is the fact that f and g are remainders modulo 15 and 30 respectively just arbitrary, or are the numbers 15 and 30 picked specifically? Algorithm 4.2 uses remainders modulo 10 and 30 instead of 15 and 30, for instance. –  CmdrMoozy May 7 '12 at 0:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.