mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2010-10-02, 14:14   #1
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default 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.

Last fiddled with by maxal on 2010-10-02 at 14:15
maxal is offline   Reply With Quote
Old 2010-10-02, 14:58   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

well to get the candidates just find k such that A*k+B are on the lines 6n+1 or 6n-1.
science_man_88 is offline   Reply With Quote
Old 2010-10-02, 16:23   #3
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

1100010112 Posts
Default

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.
Ken_g6 is offline   Reply With Quote
Old 2010-10-02, 16:40   #4
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

I'm not asking about the theory, I'm asking about the _software_.
maxal is offline   Reply With Quote
Old 2010-10-02, 16:43   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by maxal View Post
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 is offline   Reply With Quote
Old 2010-10-02, 16:44   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by maxal View Post
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.
science_man_88 is offline   Reply With Quote
Old 2010-10-02, 17:23   #7
maxal
 
maxal's Avatar
 
Feb 2005

FC16 Posts
Default

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.
maxal is offline   Reply With Quote
Old 2010-10-02, 17:41   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Old 2010-10-03, 13:44   #9
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

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.
mdettweiler is offline   Reply With Quote
Old 2010-10-03, 17:13   #10
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

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.
maxal is offline   Reply With Quote
Old 2010-10-03, 17:32   #11
axn
 
axn's Avatar
 
Jun 2003

22·17·73 Posts
Default

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

Thread Tools


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

All times are UTC. The time now is 00:11.

Sat May 15 00:11:38 UTC 2021 up 36 days, 18:52, 0 users, load averages: 2.83, 2.56, 2.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.