Professor Terry Tao of UCLA gave a presentation on prime numbers and their pseudorandomness at the latest International Math Olympiad. I had not thought about the fact that it is comparatively easy to to find a random prime number of k digits, it is much harder to deterministically find one. Click on the link to get a pdf of his presentation.