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.

[QUOTE=axn;232425]yafu has a high performance SoE. It also (most likely) has routines for modular arithmetic. Should be easy to adapt it for your purpose.[/QUOTE]
That may be a good idea, if there is no ready-to-use tool.
Another option is to adapt the PrimeGen tool [url]http://cr.yp.to/primegen.html[/url] that uses sieve of Atkin.

When Markus Frind and myself looked for a titanic AP-8 we used a four step process:
[LIST=1][*]sieve with newpgen a form with 2411# in it to give a high density[*]PRP with PFGW[*]use Markus' ap-detector on the PrP points extending beyond the range when an AP-7 was detected[*]prove the 8 PRPs[/LIST]
[url]http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0306&L=NMBRTHRY&P=R410&I=-3[/url]

What would be a cool record is a titanic AP 9. Something that should be done in this decade!

For the titanic AP-9...
[LIST][*]we would need 1.2 billion PRPs -- this is not a problem when the work is DC'd on modern hardware[*]a big machine with lots of ram and shared memory access and many cores, like the AMD chips coming out next year -- to do the AP-detection[/LIST]

[QUOTE=maxal;232424]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.[/QUOTE]

Just make a nice script, hope that it's fast, and continue on from there.

[QUOTE=maxal;232426]That may be a good idea, if there is no ready-to-use tool.
Another option is to adapt the PrimeGen tool [url]http://cr.yp.to/primegen.html[/url] that uses sieve of Atkin.[/QUOTE]

I don't know of a ready to use tool, but I also haven't looked. YAFU's SoE is pretty good, but I don't know right away what modifications would be needed to do what you need it to do, so I don't know how easy it would be to accomplish. If it comes to that I'll help you if I can. I've got modular arithmetic routines coded too, but they are home grown and likely not as fast as gmp, especially for larger [L,U]. Speaking of which, what order of magnitude are you interested in for L and U? You mention you would like the software to return primes, which for a sieve implies no more than 10^20 or so. Or would you just like less candidates to test with some other method?

[QUOTE=bsquared;232461]Speaking of which, what order of magnitude are you interested in for L and U? You mention you would like the software to return primes, which for a sieve implies no more than 10^20 or so. Or would you just like less candidates to test with some other method?[/QUOTE]
In general we can assume L=1. The order of U/A (notice that the "step" A may be large, making it possible to reach larger U) is reasonable - 10^20 or so, as you mentioned. And, indeed, the sieve may be combined with other methods, that is, it would sieve out numbers divisible by "small" primes, delegating (pseudo-)primality proofs of the remaining "candidates" to other methods (such as Miller-Rabin).

How do you do the search for arithmetic progressions in a set of numbers? There's the obvious n^2 log n approach of running through x_i, x_j for 0<i<j<N and checking 2x_j-x_i; and it feels as if it ought to be possible to use some kind of Fourier-transform autocorrelation approach, though the naive way would use memory on the order of the size of the numbers rather than on the order of the size of the set.

Can it be done in n log n time and memory?

[QUOTE=fivemack;232496]How do you do the search for arithmetic progressions in a set of numbers?[/QUOTE]
I don't, the arithmetic progression (that is, the constants A and B) is given.