
Computational Science Scientific Computing  Bioinformatics, Computational Chemistry, Computational Neuroscience, Computational Physics, Numerical Algorithms, Symbolic Mathematics, Cognitive Science 
 LinkBack  Thread Tools  Display Modes 
August 5th, 2008, 02:25 AM  #1 
Joined: Jul 2008 Posts: 13  Finding large 2primes
So a 2prime is a prime of the form 4p+3 where p and 2p+1 are also prime. It is the third in a Cunningham chain. I am looking for a way to find these around the order of maybe 2^512, if I can. I have been unable to find any so far. Does anyone know if there is a good way to do this? Has anyone looked at Cunningham chains before? Thanks, Nathan 
My Computer Forum is free to register and we welcome everyone! 
August 5th, 2008, 06:38 AM  #2 
Joined: Dec 2007 Posts: 232  Re: Finding large 2primes
It's easy enough to write a quick Pari program to find Cunningham triples. Just use nextprime and ispseudoprime (and verify primality, as needed, with a different program). But this isn't particularly fast. I estimate that my program would take my program at least 15 hours to find the first Cunningham triple after 2^512, based on the speed of finding triples near 2^128 and 2^256. I'm running a test at 2^384 right now, but that won't finish before this post  unless I'm lucky or a bad typist. A better way would be to sieve the area around 4p. A very rough heuristic suggests that a region of size 350 million would have a 50/50 chance of containing such a prime; improvements to this heuristic would suggest a somewhat better chance. The memory wouldn't be too bad, either, especially if you work mod 6 or 30. 3Cunningham chains end with primes that are 5 mod 6, and must be {17, 23, 29} mod 30; with the latter you're talking about 4 megabytes in a bit array. And wait, you can actually work mod 24 or 120 for the last one  that shaves size on the latter to barely over a megabyte. Of course sieving down to the true primes would take far too long  you'd need pi(2^256) primes  but with the first billion you've largely reduced the testing work for the pseudoprime engine. And at that point, you can use pfgw rather than Pari and get speedup that way. 
August 5th, 2008, 06:45 AM  #3 
Joined: Dec 2007 Posts: 232  Re: Finding large 2primes
Actually, I see that my program was done, after all, by the time I submitted by above post. If it was just luck, no big deal; if not, finding one around 2^512 might not take that much longer than an hour. Here's my '2prime' of probable primes (around 2^384): 39402006196394479212279040100143613805079739270465 44666794829340424572177149721061141426625488491564 0806627994687501 
August 5th, 2008, 07:23 AM  #4  
Joined: Jul 2008 Posts: 13  Re: Finding large 2primes Quote:
Thanks for the response! EDIT: Looks like that 2prime is no good, you can't have a 2prime (or 1prime) cong. to 1 mod 10 (or a 2prime to 3). You knew that, I know. I probably caught you early morning or something, so I'll let it slide..this time  
August 5th, 2008, 10:35 AM  #5  
Joined: Dec 2007 Posts: 232  Re: Finding large 2primes
Here's the one near 2^512: 13407807929942597099574024998205846127479365820592 39337772356144372176403007354697680187429816690342 76900318581864860508537538828119465699464336490449 42641 Quote:
(13:34)p384 = 39402006196394479212279040100143613805079739270465 44666794829340424572177149721061141426625488491564 0806627994687501; (13:34)ispseudoprime(p384) %25 = 1 (13:34)ispseudoprime(p384*2+1) %26 = 1 (13:34)ispseudoprime(p384*4+3) %27 = 1  
August 5th, 2008, 10:46 AM  #6  
Joined: Dec 2007 Posts: 232  Re: Finding large 2primes Quote:
A bitarray is just a bucket of bits  think bit[1000], Cstyle. Of course they're actually not stored quite like that, but that's details. The bits in the bitarray would be 0 for composite and 1 for 'maybe prime'. You might have arr[0] represent the primality of 4p+3, arr[1] represent the primality of 4p+7, and so on.  
August 5th, 2008, 02:30 PM  #7 
Joined: Jul 2008 Posts: 13  Re: Finding large 2primes
Okay, sorry, I thought you were giving me the top prime, not the bottom. *slaps head* Maybe starting at the bottom of the chain is better(?). Also, I think I worked out that, after a point, all 2primes are 47 or 119 mod 120. I think. I did manage to find 2 such primes around 2^512 in about 13 minutes. That was with a C program not yet implementing a bit array. I'm guessing I have to "roll my own" when it comes to making a bit array in C. Is that correct? EDIT: Found 47 more overnight for a total of 49. W00T! 
August 6th, 2008, 08:56 AM  #8 
Joined: Dec 2007 Posts: 232  Re: Finding large 2primes
Can you post your code? How are you checking these numbers for (pseudo)primality? I agree that the final member of the chain must be 47 or 119 mod 120, corresponding to 23 or 59 mod 60 and 11 and 29 mod 30 for the second and first members, respectively. This can be expanded from two possibilities mod 30/60/120 to eight possibilities mod 210/420/840, if desired. This would probably be the most convenient way to roll your own bitarray: make a byte array byte[LARGE_CONSTANT] and interpret each bit in the byte as a different possibility mod 210/420/840. So you would need only one array, which you would sieve three times: as 210k + offset, as 420k + offset, and as 840k + offset. 
August 6th, 2008, 09:04 AM  #9 
Joined: Jul 2008 Posts: 13  Re: Finding large 2primes
Yep, here it is: Code: #include <stdio.h> #include <gmp.h> #include <time.h> int main() { mpz_t pp; int counter; clock_t time; mpz_init(pp); mpz_set_str(pp, "502008875382777453694263747727091425699665321973957592623016585723526597309582326552318492600647489167577304855108531809162334717407620501969933757756742", 0); mpz_mul_ui(pp, pp, 120); mpz_add_ui(pp, pp, 47); counter = 0; while(counter < 21000000) { if(mpz_probab_prime_p(pp, 5)) { mpz_fdiv_q_2exp(pp, pp, 1); if(mpz_probab_prime_p(pp, 5)) { mpz_fdiv_q_2exp(pp, pp, 1); if(mpz_probab_prime_p(pp, 5)){gmp_printf("%Zd\n\n", pp);} mpz_mul_2exp(pp, pp, 1); mpz_add_ui(pp, pp, 1); } mpz_mul_2exp(pp, pp, 1); mpz_add_ui(pp, pp, 1); } mpz_add_ui(pp, pp, 72); if(mpz_probab_prime_p(pp, 5)) { mpz_fdiv_q_2exp(pp, pp, 1); if(mpz_probab_prime_p(pp, 5)) { mpz_fdiv_q_2exp(pp, pp, 1); if(mpz_probab_prime_p(pp, 5)){gmp_printf("%Zd\n\n", pp);} mpz_mul_2exp(pp, pp, 1); mpz_add_ui(pp, pp, 1); } mpz_mul_2exp(pp, pp, 1); mpz_add_ui(pp, pp, 1); } ++counter; mpz_add_ui(pp, pp, 48); } time = clock(); printf("%d ms\n", (int)time); return 0; } EDIT: You can see this from my code, but the 7 hours looked through 2.5 billion integers and 42 million candidates. 
August 6th, 2008, 10:49 AM  #10 
Joined: Dec 2007 Posts: 232  Re: Finding large 2primes
I'm a little confused by the code, since it looks like you shift your running variable pp. You're not doing that, right? That is, the 49 numbers you have are all greater than 2^507, rather than one around 2^507, one around 2^505, one around 2^503, and so on? If you like, you can drop the number of tests for the initial test to 1; you don't need much confidence here, since even if p seems to be prime you can rule it out by finding that p >> 1 or p >> 2 are composite. You can always add better tests at the end. 
August 6th, 2008, 01:28 PM  #11 
Joined: Jul 2008 Posts: 13  Re: Finding large 2primes
Yeah, this code is not good. It works, but it's not well written. All the bottom primes are 513 binary digits. I didn't plan well and ended up having to do some tricky stuff to get my powers to work out right. I should have used another variable. Don't stare too long at my code, it will make yours worse. :roll: I am working on a new version though, trying to implement this bit array thing. It's...coming. I will make sure to knock the pseudo prime test down to 1. 
August 6th, 2008, 08:13 PM  #12 
Joined: Dec 2007 Posts: 232  Re: Finding large 2primes
Incidentally, if reducing the tests from 5 to 1 gives a significant performance increase, it means that a good fraction of the numbers you're testing are being quickly discarded, before doing even one Fermat test. If there was no such testing and the program skipped right to the tests, the performance increase would be less than 1% for the size of numbers you're looking at (since primes would be rare enough that the extra time you spend on them wouldn't matter much). Also, I realized that sieving for small primes dividing 4p+3 isn't worth it, since GMP will just check that for you. The real value comes in finding when p and 2p+1 are composite but 4p+3 is prime (or a pseudoprime): GMP would have to finish a Fermat test to reject it, but you can simply test for small factors. You should probably write special code for primes under 210/420, then after that you can just move forward p/210 (resp. p/420) spaces and check p%210. OK, I don't think I'm making sense, let me mock something up: Code: const Bignum offset = 2^512 + 164; // if this isn't a multiple of 210, change the {11, 41, 89, 131, 149, 179, 191, 209} part appropriately // p is the current prime // arr[k] has bits representing offset + 210k + {11, 41, 89, 131, 149, 179, 191, 209}, where bit 1 is +11, bit 2 is +41, etc. int wholePart = p / 210; // round down int fracPart = p % 210; int cur; // current index in array int curFrac = offset % p; // current location within index cur = curFrac / 120; curFrac %= 120; while (cur < SIZE) { // This uses 1 for composite and 0 for might be prime; you could negate the hex constants and use &= instead of = if you wanted to reverse it. byte[cur] = markOff(curFrac); // Increment current location by p cur += wholePart; curFrac += fracPart; if (curFrac >= 120) { curFrac = 120; cur++; } } . . . // Basic binary search, specialized for these values byte markOff(int f) { if (f < 132) { if (f < 66) { if (f == 11) return 0x01; else if (f == 41) return 0x02; } else { if (f == 89) return 0x04; else if (f == 131) return 0x08; } } else { if (f < 180) { if (f == 149) return 0x10; else if (f == 179) return 0x20; } else { if (f == 191) return 0x40; else if (f == 209) return 0x80; } } return 0x00; } 
August 7th, 2008, 02:22 AM  #13 
Joined: Jul 2008 Posts: 13  Re: Finding large 2primes
Ooh, I see. So what would be ideal would be if GMP could do just trial division, no other tests. Maybe setting the parameter to 0 would do this. I haven't found that explicitly in the documentation, but it definitely seems that that would be the case.

August 7th, 2008, 06:03 AM  #14  
Joined: Dec 2007 Posts: 232  Re: Finding large 2primes Quote:
 

Tags 
2primes, finding, large 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
help me for finding gboxapp software  jamiulislam  Computer Science  0  January 21st, 2013 03:02 AM 
Help in finding a high performance notebook!  deanSs  Computer Hardware  2  February 9th, 2012 01:55 PM 
Finding an acyclic orientation in a graph  Anonymous Coward  Algorithms  7  January 24th, 2010 01:28 PM 
Finding clusters of points on a grid  circleBounding  Algorithms  2  February 10th, 2008 06:09 PM 