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
April 2nd, 2008, 06: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 (Ballie-PSW 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.
CRGreathouse is offline  
 

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

April 3rd, 2008, 07: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.)
cknapp is offline  
April 3rd, 2008, 09:05 PM   #3
 
Joined: Dec 2007
Posts: 232
Re: Pseudoprime testing?

Quote:
Originally Posted by cknapp
You could always write a bignum package and a pseudoprime testing algorithm that takes advantage of powers of 2.
It's tempting. Of course I don't know of a good enough algorithm.

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 level-index arithmetic system as an undergrad class project. So I'm not quite the neophyte I might have appeared to be.
CRGreathouse is offline  
July 26th, 2008, 04: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?
yttrium88 is offline  
July 26th, 2008, 07: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 dual-boot 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.
CRGreathouse is offline  
July 27th, 2008, 09: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...
cknapp is offline  
July 29th, 2008, 08: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.)
CRGreathouse is offline  
March 6th, 2009, 03: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
lpholds is offline  
March 8th, 2009, 04: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.
CRGreathouse is offline  
Reply

  My Computer Forum > Computer Science Forum > Computational Science

Tags
pseudoprime, testing



Thread Tools
Display Modes






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