
Computational Science Scientific Computing  Bioinformatics, Computational Chemistry, Computational Neuroscience, Computational Physics, Numerical Algorithms, Symbolic Mathematics, Cognitive Science 
 LinkBack  Thread Tools  Display Modes 
April 2nd, 2008, 07:23 AM  #1 
Joined: Dec 2007 Posts: 232  Pseudoprime testing?
I'm looking for a way to test large numbers for pseudoprimality. Any ideas on what program/package is fastest at this? I've been running a single candidate for over a month now on Pari/GP (BalliePSW pseudoprime test), which is excellent for numbers below a kilobyte or so, but slows down quite a bit for big stuff. This particular number is 166,031 digits long (67 kB). If it matters, it's close to a power of 2  but I don't know if any good pseudoprime tests take advantage of that kind of 'SNFS' relation. 
My Computer Forum is free to register and we welcome everyone! 
April 3rd, 2008, 08:34 AM  #2 
Joined: Dec 2007 Posts: 138  Re: Pseudoprime testing?
You could always write a bignum package and a pseudoprime testing algorithm that takes advantage of powers of 2. I know, I'm not helpful at all... The only things I can really think of that might be useful are Pari, Maple, and C (mostly because there's likely a package for it). Haskell is really good for certain types of computation; but I couldn't tell you what those types are, or if this is among them (or if someone has written a package for it.) 
April 3rd, 2008, 10:05 PM  #3  
Joined: Dec 2007 Posts: 232  Re: Pseudoprime testing? Quote:
I might very well write a bignum package, though. It wouldn't be nearly fast enough to be competitive, but it would be a good exercise. I have written a decent set of integer functions with fast algorithms, and I wrote a basic levelindex arithmetic system as an undergrad class project. So I'm not quite the neophyte I might have appeared to be.  
July 26th, 2008, 05:16 AM  #4 
Joined: Jul 2008 Posts: 7  Re: Pseudoprime testing?
EDIT: Wow. I just realized that this is a very old thread. So...did you get that number proven composite yet? I'm sure I'm more than a little naïve when it comes to this caliber of computation, but I'll just throw it out there that I had good luck using the GNU Multiprecision (GMP) library in some C programs this past week (after reaching the limit of my patience with the pari library). I don't know if this is quite what you are looking for, but it has support for more sophisticated calculations than I was expecting and I believe the authors of Pari/GP admit that it is slightly faster than their multiprecision engine. Anyway, I got it to run under Cygwin and gcc with no problems. On another note, this number is waaay out of the range of Primo, correct? So, if I may ask, what are you planning on doing with such a large prime as this? Also, what kind of machine are you running the test with pari/gp on? 
July 26th, 2008, 08:53 PM  #5 
Joined: Dec 2007 Posts: 232  Re: Pseudoprime testing?
I don't think I ever managed to find a system to test the number on. I gave up after a fair amount of computation. I haven't been able to get GMP running on Windows via cygwin. That's OK, I'll probably move to dualboot with Xubuntu soon and do it 'the right way'. The number is out of Primo's range, yes; now it does only < 10,000 digits. But that would prove primality, and while that would be great I'm willing to settle for a good pseudoprimality result. The number was for a Sloane sequence. 
July 27th, 2008, 10:06 AM  #6 
Joined: Dec 2007 Posts: 138  Re: Pseudoprime testing?
Charles, if you don't mind my asking: What do you get paid to do? I've been interested in this for quite a while now... 
July 29th, 2008, 09:13 PM  #7 
Joined: Dec 2007 Posts: 232  Re: Pseudoprime testing?
I'm a programmer for the safety department at a research university. Actually, to be honest, I don't do a whole lot of programming per se at this job; I mostly keep my skills up to date on my own. I do more work with databases and our web site than with 'real' programming, and I do more than just computer work. (I do safety work, natch.)

March 6th, 2009, 04:37 AM  #8 
Joined: Mar 2009 Posts: 1  pseudonumber
Hi!! what about this? construct your own pseudo number generator.Base the generator on the linear congruential method Ij+i=aIj(mod m) with m=8192 and a=125 
March 8th, 2009, 05:35 PM  #9 
Joined: Dec 2007 Posts: 232  Re: Pseudoprime testing?
Because I want to test a number for pseudoprimality, not generate a pseudorandom number. Plus, linear congruential generators aren't that great. 