Pseudoprime testing?

[CRGreathouse]

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.

[cknapp]

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.)

[CRGreathouse]

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.

[yttrium88]

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?

[CRGreathouse]

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.

[cknapp]

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...

[CRGreathouse]

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.)

[lpholds]

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

[CRGreathouse]

Because I want to test a number for pseudoprimality, not generate a pseudorandom number.

Plus, linear congruential generators aren't that great.