Primality Testing
- Submitted by: kyla0412
- Views: 437
- Category: Politics: Philosophy
- Date Submitted: 11/06/2011 06:47 AM
- Pages: 11
- Report this Essay
Introduction
Primality testing of a number is perhaps the most common problem concerning number theory that topcoders deal with. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. Some basic algorithms and details regarding primality testing and factorization can be found here.
The problem of detecting whether a given number is a prime number has been studied extensively but nonetheless, it turns out that all the deterministic algorithms for this problem are too slow to be used in real life situations and the better ones amongst them are tedious to code. But, there are some probabilistic methods which are very fast and very easy to code. Moreover, the probability of getting a wrong result with these algorithms is so low that it can be neglected in normal situations.
This article discusses some of the popular probabilistic methods such as Fermat's test, Rabin-Miller test, Solovay-Strassen test.
Modular Exponentiation
All the algorithms which we are going to discuss will require you to efficiently compute (ab)%c ( where a,b,c are non-negative integers ). A straightforward algorithm to do the task can be to iteratively multiply the result with 'a' and take the remainder with 'c' at each step.
/* a function to compute (ab)%c */
int modulo(int a,int b,int c){
// res is kept as long long because intermediate results might overflow in "int"
long long res = 1;
for(int i=0;i<b;i++){
res *= a;
res %= c; // this step is valid because (a*b)%c = ((a%c)*(b%c))%c
}
return res%c;
}
However, as you can clearly see, this algorithm takes O(b) time and is not very useful in practice. We can do it in O( log(b) ) by using what is called as exponentiation by squaring. The idea is very simple:
(a2)(b/2)...
Primality testing of a number is perhaps the most common problem concerning number theory that topcoders deal with. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. Some basic algorithms and details regarding primality testing and factorization can be found here.
The problem of detecting whether a given number is a prime number has been studied extensively but nonetheless, it turns out that all the deterministic algorithms for this problem are too slow to be used in real life situations and the better ones amongst them are tedious to code. But, there are some probabilistic methods which are very fast and very easy to code. Moreover, the probability of getting a wrong result with these algorithms is so low that it can be neglected in normal situations.
This article discusses some of the popular probabilistic methods such as Fermat's test, Rabin-Miller test, Solovay-Strassen test.
Modular Exponentiation
All the algorithms which we are going to discuss will require you to efficiently compute (ab)%c ( where a,b,c are non-negative integers ). A straightforward algorithm to do the task can be to iteratively multiply the result with 'a' and take the remainder with 'c' at each step.
/* a function to compute (ab)%c */
int modulo(int a,int b,int c){
// res is kept as long long because intermediate results might overflow in "int"
long long res = 1;
for(int i=0;i<b;i++){
res *= a;
res %= c; // this step is valid because (a*b)%c = ((a%c)*(b%c))%c
}
return res%c;
}
However, as you can clearly see, this algorithm takes O(b) time and is not very useful in practice. We can do it in O( log(b) ) by using what is called as exponentiation by squaring. The idea is very simple:
(a2)(b/2)...