Not sure if this has been posted or not.. but i was refered to this paper about new method of primality testing which is very fast.
http://www.cse.iitk.ac.in/news/primality.pdf

Actually, it's not fast at all. There are probablistic tests that run orders of magnitude faster. But they can only say that a number is "probably" prime (albeit with a very high confidence level). This paper's important because it gives an algorithm that is guaranteed to run in less than a fixed constant times the number of bits to the twelfth power (rather than exponential in the number of bits) and is guaranteed to give the right answer.