Fast primality test for small numbers

CRGreathouse

I'm looking for a library (or just a program) with a fast primality test for 64-bit numbers. In particular I'd like something that's faster than Pari which I'm currently using. I do need it to be programmable, of course, since billions of tests need to be done.

Any ideas? Or is Pari essentially as fast as I can get?

I'm going to try to port my program to Mathematica to do a speed comparison, but in past tests Pari beats Mathematica soundly in number theory.

CRGreathouse

Original Pari code:

Code:

aa=vector(90,n,2^n);bb=vector(90,n,3*2^n);v=sumset(aa,bb);v=vector(5000,i,v[i]);
counter(n)=my(i=0);while(v[i++]<n,if(isprime(n-v[i]),return(0)));1
forstep(n=7,1e6,2,if(counter(n),print(n)))

This actually uses my custom function sumset, but its function is pretty clear from context.

Here's my Mathematica version:

Code:

v=Part[Sort[Flatten[Table[2^i+3*2^j,{i,90},{j,90}]]],1;;5000];
counter(n_):=Block[{i=0},
	While[v[[i++]]<n,
		If[PrimeQ[n-v[[i]]],Return[0]]
	];
	Return[1]
]
Timing[For[i=7,i<=10^6,i+=2,If[counter[i]!=0,Print[i]]]]

The Mathematica code takes about three times as long as the Pari code. The Pari code could be yet faster with ispseudoprime, of course...

Similar discussions for: Fast primality test for small numbers
Thread	Forum	Replies
Euler's theorem as primality test?	Linear & Abstract Algebra	6
Finding small primes (fast determanistic tests)	Linear & Abstract Algebra	11
Another (candidate) test of primality of Mersenne number	Linear & Abstract Algebra	11
strong primality test ... ??	Introductory Physics Homework	2
A primality test for Fermat numbers faster than Pépin's test ?	Linear & Abstract Algebra	2