Fast primality test for small numbers

In summary, the conversation is about finding a fast primality test for 64-bit numbers. The person is currently using Pari but is looking for something faster. They mention trying to compare speeds with Mathematica, but state that Pari usually beats it in number theory. The original Pari code and a corresponding Mathematica version are provided for reference.
  • #1
CRGreathouse
Science Advisor
Homework Helper
2,844
0
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:
Physics news on Phys.org
  • #2
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...
 

Related to Fast primality test for small numbers

1. What is a fast primality test for small numbers?

A fast primality test for small numbers is a method used to determine if a given number is prime or not. It is specifically designed to work efficiently for small numbers, which are typically defined as numbers less than 10 million.

2. How does a fast primality test for small numbers work?

A fast primality test for small numbers works by using a set of predetermined rules and algorithms to quickly determine if a number is divisible by any other number besides 1 and itself. This is done by checking if the number is divisible by any prime number up to its square root.

3. Why is a fast primality test useful for small numbers?

A fast primality test for small numbers is useful because it can quickly determine if a number is prime or not, which is important for many mathematical and computational applications. It also allows for more efficient and faster calculations when working with small numbers.

4. Are there different types of fast primality tests for small numbers?

Yes, there are various types of fast primality tests for small numbers, such as the Sieve of Eratosthenes, the Miller-Rabin primality test, and the Lucas-Lehmer primality test. Each method has its own set of advantages and disadvantages, but all are designed to efficiently determine the primality of small numbers.

5. Is a fast primality test for small numbers always accurate?

Yes, a fast primality test for small numbers is always accurate. However, it should only be used for small numbers, as it may not be as efficient or accurate for larger numbers. For larger numbers, more complex and accurate primality tests should be used.

Similar threads

  • Programming and Computer Science
Replies
30
Views
4K
  • Linear and Abstract Algebra
Replies
4
Views
3K
  • General Math
Replies
16
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
4
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
7K
  • STEM Academic Advising
Replies
21
Views
2K
  • Biology and Medical
3
Replies
100
Views
6K
Replies
6
Views
841
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Back
Top