This is the topic on which three indian students created history by giving AKS algorithm.
The topic is very interseting.This is the problem to find large primes. Cryptography requires the implentation
of larger primes. The prime distribution function pie(n) specifies the number of primes that r less than or equal to n. e.g pi(10)=4, since there r 4 primes numbers less than or equal to 10., namely 2,3, 5,7. so the ttheorem
prime number theorem:
lim(n-> infinity) pi(n)/(n/ln n) =1
we can use the prime number theorem to estimate the probability that a randomly chosen integer n will turn out to be prime as 1/ln n .
One simple approach to the problem of testing for primality is trial division. We try dividing n by each integer 2, 3,….sqrt(n). Again , even integers greater than 2 may be skipped.
Demerit : It is easy to see that trial division works well only if n is very small or happen to have small prime factor.
We will se further that computing the prime factorization of a number is compuationally expensive. It is perhaps surprising that it is much easier to tell whetther or not a given number is prime than it is to detemine the prime factorization of the number if it is not prime.
rest we will talk about Pseudoprimality Testing