My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Computational Science

Computational Science Scientific Computing - Bioinformatics, Computational Chemistry, Computational Neuroscience, Computational Physics, Numerical Algorithms, Symbolic Mathematics, Cognitive Science


Reply
 
LinkBack Thread Tools Display Modes
August 5th, 2008, 01:25 AM   #1
 
Joined: Jul 2008
Posts: 13
Finding large 2-primes

So a 2-prime 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
NClement is offline  
 

My Computer Forum is free to register and we welcome everyone!

August 5th, 2008, 05:38 AM   #2
 
Joined: Dec 2007
Posts: 232
Re: Finding large 2-primes

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. 3-Cunningham 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.
CRGreathouse is offline  
August 5th, 2008, 05:45 AM   #3
 
Joined: Dec 2007
Posts: 232
Re: Finding large 2-primes

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 '2-prime' of probable primes (around 2^384):
39402006196394479212279040100143613805079739270465 44666794829340424572177149721061141426625488491564 0806627994687501
CRGreathouse is offline  
August 5th, 2008, 06:23 AM   #4
 
Joined: Jul 2008
Posts: 13
Re: Finding large 2-primes

Quote:
Originally Posted by CRGreathouse
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.
I would be interested to know how you get this heuristic, why 4p? Also, I'm going to look up the concept of bit array, but could you (or someone else) just give me a quick on sentence description on what it is and how to apply it in this case. I'm assuming this is bits with isprime(p)&&isprime(p>>1)&&isprime(p>>2).

Thanks for the response!

EDIT: Looks like that 2-prime is no good, you can't have a 2-prime (or 1-prime) cong. to 1 mod 10 (or a 2-prime to 3). You knew that, I know. I probably caught you early morning or something, so I'll let it slide..this time
NClement is offline  
August 5th, 2008, 09:35 AM   #5
 
Joined: Dec 2007
Posts: 232
Re: Finding large 2-primes

Here's the one near 2^512:
13407807929942597099574024998205846127479365820592 39337772356144372176403007354697680187429816690342 76900318581864860508537538828119465699464336490449 42641

Quote:
Originally Posted by NClement
EDIT: Looks like that 2-prime is no good, you can't have a 2-prime (or 1-prime) cong. to 1 mod 10 (or a 2-prime to 3). You knew that, I know. I probably caught you early morning or something, so I'll let it slide..this time
Huh? The initial prime must be 1 or 9 mod 10, and must be 2 mod 3.

(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
CRGreathouse is offline  
August 5th, 2008, 09:46 AM   #6
 
Joined: Dec 2007
Posts: 232
Re: Finding large 2-primes

Quote:
Originally Posted by NClement
Quote:
Originally Posted by CRGreathouse
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.
I would be interested to know how you get this heuristic, why 4p? Also, I'm going to look up the concept of bit array, but could you (or someone else) just give me a quick on sentence description on what it is and how to apply it in this case. I'm assuming this is bits with isprime(p)&&isprime(p>>1)&&isprime(p>>2).
For a given prime p, I'm checking if 2p+1 and 4p+3 are prime. Since you'll probably need to check many numbers in each range, it makes sense to build tables around each region you're checking. The largest one will be the highest, so I said 4p rather than p, 2p, and 4p.

A bitarray is just a bucket of bits -- think bit[1000], C-style. 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.
CRGreathouse is offline  
August 5th, 2008, 01:30 PM   #7
 
Joined: Jul 2008
Posts: 13
Re: Finding large 2-primes

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 2-primes 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!
NClement is offline  
August 6th, 2008, 07:56 AM   #8
 
Joined: Dec 2007
Posts: 232
Re: Finding large 2-primes

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.
CRGreathouse is offline  
August 6th, 2008, 08:04 AM   #9
 
Joined: Jul 2008
Posts: 13
Re: Finding large 2-primes

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;
}
The pseudo-prime function is mpz_probab_prime_p(), with a parameter of 5 (they recommend 5-10). Documentation says that this does trial division then Miller-Rabin tests. So that 47 figure is for 7 hours of processing. 15 minutes this morning was enough for Pari verify true 2-primality for all 49.

EDIT: You can see this from my code, but the 7 hours looked through 2.5 billion integers and 42 million candidates.
NClement is offline  
August 6th, 2008, 09:49 AM   #10
 
Joined: Dec 2007
Posts: 232
Re: Finding large 2-primes

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.
CRGreathouse is offline  
August 6th, 2008, 12:28 PM   #11
 
Joined: Jul 2008
Posts: 13
Re: Finding large 2-primes

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.
NClement is offline  
August 6th, 2008, 07:13 PM   #12
 
Joined: Dec 2007
Posts: 232
Re: Finding large 2-primes

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;
}
CRGreathouse is offline  
August 7th, 2008, 01:22 AM   #13
 
Joined: Jul 2008
Posts: 13
Re: Finding large 2-primes

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.
NClement is offline  
August 7th, 2008, 05:03 AM   #14
 
Joined: Dec 2007
Posts: 232
Re: Finding large 2-primes

Quote:
Originally Posted by NClement
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.
You don't want that, though, because then your false positives would skyrocket. Right now you might expect 70-80 true positives and, say, 0.000001 false positives; if you did 0 Fermat tests you might get a million false positives -- and getting this few would require testing for primes up to a billion or so (which would almost surely be slower than a real Fermat test). Memory aside, though, this would give a substantial speedup -- it might run ten to a hundred times faster. It's just that it would be worthless, as all the false positives would swamp the true positives.
CRGreathouse is offline  
Reply

  My Computer Forum > Computer Science Forum > Computational Science

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 02:02 AM
Help in finding a high performance notebook! deanSs Computer Hardware 2 February 9th, 2012 12:55 PM
Finding an acyclic orientation in a graph Anonymous Coward Algorithms 7 January 24th, 2010 12:28 PM
Finding clusters of points on a grid circleBounding Algorithms 2 February 10th, 2008 05:09 PM





Copyright © 2018 My Computer Forum Forum. All rights reserved.