Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fast primality test for small numbers

  1. Jan 27, 2009 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Beating Pari: fast primality test for small numbers

    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.
     
    Last edited: Jan 27, 2009
  2. jcsd
  3. Jan 28, 2009 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Original Pari code:
    Code (Text):
    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 (Text):
    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...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?