sieving primes in arithmetic progressions

maxal · 2010-10-02, 14:14

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.

science_man_88 · 2010-10-02, 14:58

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

Ken_g6 · 2010-10-02, 16:23

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

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 Modular multiplicative inverse. Those take a little more work, but they can be worth it. Especially if A is of a special form that makes it easy.

maxal · 2010-10-02, 16:40

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

science_man_88 · 2010-10-02, 16:43

Quote:

Originally Posted by maxal

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

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

science_man_88 · 2010-10-02, 16:44

Quote:

Originally Posted by maxal

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

http://www.google.ca/search?hl=en&q=...=&oq=&gs_rfai=

theres possible answers.

maxal · 2010-10-02, 17:23

science_man_88, 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.

science_man_88 · 2010-10-02, 17:41

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.

mdettweiler · 2010-10-03, 13:44

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 AP26 subproject forum about it.

maxal · 2010-10-03, 17:13

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.

axn · 2010-10-03, 17:32

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

2010-10-02, 14:14	#1
maxal Feb 2005 2²·3²·7 Posts	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 Ak + 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. Last fiddled with by maxal on 2010-10-02 at 14:15*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Arithmetic progressions for n	MattcAnderson	MattcAnderson	28	2017-05-08 20:58
Compositions of arithmetic progressions	jasonp	Factoring	8	2011-08-20 13:42
Sieving for primes	CRGreathouse	Math	0	2009-01-06 14:38
Detecting arithmetic progressions	grandpascorpion	Math	18	2007-03-28 15:08
Arithmetic and Polynomial Progression of Primes?	drake2	Math	13	2006-10-10 00:43

2010-10-02, 14:58	#2
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶·131 Posts	well to get the candidates just find k such that A*k+B are on the lines 6n+1 or 6n-1.

2010-10-02, 16:23	#3
Ken_g6 Jan 2005 Caught in a sieve 613₈ Posts	Hm, that kinda looks like k2^n+1, doesn't it? I may know something about this. Let's see...you want to find: kA+B = 0 (mod P) kA = -B (mod P) k = -BA^-1 (mod P) Now, -B (mod P) is just P-B, assuming B < P. A^-1, on the other hand, is a Modular multiplicative inverse. Those take a little more work, but they can be worth it. Especially if A is of a special form that makes it easy.

2010-10-02, 16:40	#4
maxal Feb 2005 2²·3²·7 Posts	I'm not asking about the theory, I'm asking about the _software_.

2010-10-02, 17:23	#7
maxal Feb 2005 11111100₂ Posts	science_man_88, 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.

2010-10-02, 17:41	#8
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶·131 Posts	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.

2010-10-03, 13:44	#9
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3·2,083 Posts	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 AP26 subproject forum about it.

2010-10-03, 17:13	#10
maxal Feb 2005 2²·3²·7 Posts	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.

2010-10-03, 17:32	#11
axn Jun 2003 3×5×17×19 Posts	yafu has a high performance SoE. It also (most likely) has routines for modular arithmetic. Should be easy to adapt it for your purpose.