sieving primes in arithmetic progressions
 

Does there exist a fast optimized siever for finding primes in a given arithmetic progression?

That is, for given the parameters A, B along with the range [L,U], such siever should find and report all primes of the form A*k + B in the interval [L,U].

It is not a big deal to write my own siever (based on ala sieve of Eratosthenes or Atkin) but I'd rather use a fast existing siever if there is such a beast.

well to get the candidates just find k such that A*k+B are on the lines 6n+1 or 6n-1.

Hm, that kinda looks like k*2^n+1, doesn't it? I may know something about this. :wink:

Let's see...you want to find:

k*A+B = 0 (mod P)
k*A = -B (mod P)
k = -B*A^-1 (mod P)

Now, -B (mod P) is just P-B, assuming B < P. A^-1, on the other hand, is a [url=http://en.wikipedia.org/wiki/Modular_multiplicative_inverse]Modular multiplicative inverse[/url]. Those take a little more work, but they can be worth it. Especially if A is of a special form that makes it easy.

I'm not asking about the theory, I'm asking about the _software_.

[QUOTE=maxal;232348]I'm not asking about the theory, I'm asking about the _software_.[/QUOTE]

well the first thing the software needs is theory I'm not sure if there is one.

[QUOTE=maxal;232348]I'm not asking about the theory, I'm asking about the _software_.[/QUOTE]

[url]http://www.google.ca/search?hl=en&q=%22sieving%22+%22arithmetic+progressions%22+%2B+%22software%22&aq=f&aqi=&aql=&oq=&gs_rfai=[/url]


theres possible answers.

[b]science_man_88[/b], I asked concrete question about the software - if you don't know the answer, please don't make irrelevant comments.
And please don't teach me the theory - believe me, I know it well.

look if you want a siever either build one if you can or look as apparently nothing else is what you want so why post it here.

PrimeGrid did a big search for an AP26 earlier this year; I'm not sure how they went about doing it, but I would assume that a fast sieve was part of it somewhere along the way. You might try asking in their [url=http://www.primegrid.com/forum_forum.php?id=38]AP26 subproject forum[/url] about it.

AP26 is irrelevant. I'm not looking for primes forming an arithmetic progression, but primes in the given arithmetic progression (possibly with gaps between them). The latter problem is much simpler than the former one.

yafu has a high performance SoE. It also (most likely) has routines for modular arithmetic. Should be easy to adapt it for your purpose.